Theory of Computation MCQ with Answers pdf - Set 05 - ObjectiveBooks
Theory of Computation MCQ with Answers pdf - Set 05

Theory of Computation MCQ with Answers pdf - Set 05

Practice Test: Question Set - 05

1. L = (an bn an | n = 1,2,3)  is an example of a language that is
    (A) Context free
    (B) Not context free
    (C) Not context free but whose complement is CF
    (D) Both (b) and (c)
2. The set of all strings over the alphabet S = {a, b} (including e) is denoted by
    (A) (a + b)*
    (B) (a + b)+
    (C) a+b+
    (D) a*b*
3. Which of the following strings is not generated by the following grammar? S ? SaSbS|e
    (A) aabb
    (B) abab
    (C) aababb
    (D) aaabb
4. If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
    (A) L1 L2
    (B) L1  ∩ L2
    (C) L1 ∩ R
    (D) L1 ∪ L2
5. Which of the following regular expression identity is true?
    (A) r(*) = r*
    (B) (r*s*)* = (r + s)*
    (C) (r + s)* = r* + s*
    (D) r*s* = r* + s*
6. The logic of pumping lemma is a good example of
    (A) Pigeon-hole principle
    (B) Divide-and-conquer technique
    (C) Recursion
    (D) Iteration
7. Consider a grammar :

    G = ( { x , y ) , { s , x , y } , p ,  s)
    where elements of parse :
    S--> x y
    S -->y x
     x--> x z
     x--> x
     y--> y
     z--> z
The language L generated by G most accurately is called

    (A) Chomsky type 0
    (B) Chomsky type 1
    (C) Chomsky type 2
    (D) Chomsky type 3
8. Consider the following CFG

    S ? aB S ? bA

    B ? b A ? a
    B ? bS A ? aS
    B ? aBB A ? bAA

Consider the following derivation

    S ? aB
    ? aaBB
    ? aaBb
    ? aabSb
    ? aabbAb
    ? aabbab

This derivation is

    (A) A leftmost derivation
    (B) A rightmost derivation
    (C) Both leftmost and rightmost derivation
    (D) Neither leftmost nor rightmost derivation
9. Context-free grammar can be recognized by
    (A) Finite state automation
    (B) 2-way linear bounded automata
    (C) Push down automata 
    (D) Both (b) and (c)
10. What is the highest type number which can be applied to the following grammar?

    S —> Aa, A —> Ba, B —> abc

    (A) Type 0
    (B) Type 1
    (C) Type 2
    (D) Type 3
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests: