Header Ads

ad728
  • Latest

    Formal Languages And Automation Theory MCQs 1

      Formal Languages And Automation Theory MCQs

    1





    Q1. Given Grammar: S->A, A->aA, A->e, B->bA

    Which among the following productions are Useless productions?

    a) S->A

    b) A->aA

    c) A->e

    d) B->bA 

    Answer is d) B->bA
    Explanation : Some derivations are not reachable from the starting variable. As B is not reachable from the starting variable, it is a useless symbol and thus, can be eliminated.

     

    Q2. Consider the following language

    L = {
    a^nb^n|n = 1}

    L is

    a) CFL but not regular 

    b) CSL but not CFL

    c) regular

    d) type 0 language but not type 1


    Answer is a) CFL but not regular
    Explanation : For explanation Join the discussion below

     

    Q3. Consider the following language

    L = {a^nb^mc^pd^q|n, m, p, q = 1}
    L is

    a) CFL but not regular

    b) CSL but not CFL

    c) regular 

    d) type 0 language but not type 1


    Answer is c) regular
    Explanation : For explanation Join the discussion below

     

    Q4. The following CFG is in

    S ? AB
    B ? CD
    B ? AD
    B ? b
    D ? AD
    D ? d
    A ? a
    C ? a

    a) Chomsky normal form but not strong Chomsky normal form

    b) Weak Chomsky normal form but not Chomsky normal form

    c) Strong Chomsky normal form 

    d) Greibach normal form


    Answer is c) Strong Chomsky normal form
    Explanation : For explanation Join the discussion below

     

    Q5. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below: (GATE CS 2009)

    L1 = {a^mb^mca^nb^n | m, n >= 0 }
    L2 = {a^ib^jc^k | i, j, k >= 0 }
    Then L is :

    a) Not recursive

    b) Regular

    c) Context free but not regular 

    d) Recursively enumerable but not context free.


    Answer is c Context free but not regular
    Explanation : The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is L1 ∩L2 = {a^kb^kc | k >= 0} which is context free, but not regular.

     

    Q6. Match all items in Group 1 with correct options from those given in Group 2.
    Group 1    Group 2

    P. Regular expression       1. Syntax analysis

    Q. Pushdown automata     2. Code generation

    R. Dataflow analysis      3. Lexical analysis

    S. Register allocation      4. Code optimization

    a) P-4. Q-1, R-2, S-3

    b) P-3, Q-1, R-4, S-2 

    c) P-3, Q-4, R-1, S-2

    d) P-2, Q-1, R-4, S-3


    Answer is b) P-3, Q-1, R-4, S-2
    Explanation : For explanation Join the discussion below

     

    Q7. Given:

    S->aSb
    S->e
    S-> A
    A->aA
    B->C
    C->D
    The ratio of number of useless variables to number of useless production is:

    a) 1 

    b) 3/4

    c) 2/3

    d) 0


    Answer is a) 1
    Explanation : A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will never produce a string to the grammar.

     

    Q8. The following CFG is in

    S ? aBB
    B ? bAA
    A ? a
    B ? b

    a) Chomsky normal form but not strong Chomsky normal form

    b) Weak Chomsky normal form but not Chomsky normal form

    c) Strong Chomsky normal form

    d) Greibach normal form 


    Answer is d) Greibach normal form
    Explanation : For explanation Join the discussion below

     

    Q9. Which of the following CF language is inherently ambiguous?

    a) {anbncmdm|n, m = 1}

    b) {anbmcpdq|n = p or m = q, n, m, p, q = 1} 

    c) {anbmcpdq|n ? m ? p ? q}

    d) {anbmcpdq|n ? m ? p ? q}


    Answer is b) {anbmcpdq|n = p or m = q, n, m, p, q = 1}
    Explanation : For explanation Join the discussion below

     

    Q10. Given grammar G:

    S->aS|A|C
    A->a
    B->aa
    C->aCb
    Find the set of variables thet can produce strings only with the set of terminals.

    a) {C}

    b) {A,B}

    c) {A,B,S} 

    d) None of the mentioned


    Answer is c) {A,B,S}
    Explanation : First step: Make a set of variables that directly end up with a terminal Second step: Modify the set with variables that produce the elements of above generated set.
    The rest variables are termed as useless.

     

    Q11. Which one of the following is FALSE?

    a) There is unique minimal DFA for every regular language

    b) Every NFA can be converted to an equivalent PDA.

    c) Complement of every context-free language is recursive.

    d) Every nondeterministic PDA can be converted to an equivalent deterministic PDA. 


    Answer is d) Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
    Explanation : Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

     

    Q12. Can a DFSA simulate a NFSA

    a) No

    b) Yes 

    c) sometimes

    d) depends on NFA


    Answer is b) Yes
    Explanation : For explanation Join the discussion below

     

    Q13. Inorder to simplify a context free grammar, we can skip the following operation:

    a) Removal of null production

    b) Removal of useless symbols

    c) Removal of unit productions

    d) None of the mentioned 


    Answer is d) None of the mentioned
    Explanation : Inorder to simplify the grammar all of the process including the removal of null productions, unit productions and useless symbols is necessary.

     

    Q14. The concept of FSA is much used in this part of the compiler

    a) Lexical analysis 

    b) Parser

    c) Code generation

    d) Code optimization


    Answer is a) Lexical analysis
    Explanation : lexical analysis uses the concept of FSA

     

    Q15. The concept of grammar is much used in this part of the compiler

    a) Lexical analysis

    b) Parser 

    c) Code generation

    d) Code optimization


    Answer is b) Parser
    Explanation : Parser uses the concept of grammar. a parsing expression grammar (PEG), is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

     


    No comments

    Post Top Ad

    ad728

    Post Bottom Ad

    ad728