Theory of Computation MCQ Questions with Answers - Set 06 - ObjectiveBooks
Theory of Computation MCQ Questions with Answers - Set 06

Theory of Computation MCQ Questions with Answers - Set 06

Practice Test: Question Set - 06

1. The concept of grammar is much used in this part of the compiler
    (A) Lexical analysis
    (B) Parser
    (C) Code generation
    (D) Code optimization
2. Which of the following CFG's can't be simulated by an FSM?
    (A) S --> Sa | b
    (B) S  --> aSb | ab
    (C) S --> abX,  X --> cY,  Y --> d | aX
    (D) None of these
3. The productions

    E—>E+E
    E—>E—E
    E-->E*E
    E —> E / E
    E —> id

    (A) Generate an inherently ambiguous language
    (B) Generate an ambiguous language but not inherently so
    (C) Are unambiguous
    (D) Can generate all possible fixed length valid computation for carrying out addition, subtraction, multiplication and division, which can be expressed in one expression
4. Consider the following right-linear grammar G = (N, T, P, S) N = {S}

    P : S ? aS|aA T = {a, b}

    A ? bA|b

Which of the following regular expression denotes L(G)?

    (A) (a + b)*
    (B) a(ab)*b
    (C) aa*bb*
    (D) a*b*
5. Define for the context free language

    L< {0;1} init (L) =  { u | u v   ε  L for some v in {0, 1}}

If L { w | w is nonempty and has an equal number of 0's and 1's}, then init (L) is set of all binary strings

    (A) With unequal numbers of 0's and 1's
    (B) Including the null string
    (C) Both (a) and (b)
    (D) None of these
6. Set of regular languages over a given alphabet set is closed under
    (A) Union
    (B) Complementation
    (C) Intersection
    (D) All of these
7. 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
8. In a context-free grammar
    (A) ε can't be the right hand side of any production
    (B) Terminal symbols can't be present in the left hand side of any production
    (C) Number of grammar symbols in the left hand side is not greater than the number of grammar symbols in the right hand side
    (D) All of these
9. Which of the following regular expressions denotes a language comprising of all possible strings over S = {a, b} of length where n is a multiple of 3.
    (A) (a + b + aa + bb + aba + bba)*
    (B) (aaa + bbb)*
    (C) ((a + b)(a + b)(a + b))*
    (D) (aaa + ab + a) + (bbb + bb + a)
10. Context free grammar is not closed under
    (A) Product
    (B) Union
    (C) Complementation 
    (D) Kleene Star

Show and hide multiple DIV using JavaScript View All Answers
 Next Tests: