Theory of Computation and Compiler Design 02

11. The equivalent grammar corresponding to the grammar  G : S → aA, A → BB, B → aBb | ϵ is                                                                                                 [Paper III June 2012]

(A) S →  aA,     A →  BB,     B →  aBb

(B) S → a | aA,    A → BB,     B → aBb | ab

(C) S → a | aA,    A → BB | B,     B → aBb

(D) S → a | aA,    A → BB | B,     B → aBb | ab

12. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains                                                                      [Paper III June 2012]

(A) n states                  (B) n + 1 states

(C) n + 2 states            (D) 2n states

13. The following CFG S → aB | bA, A → a | as | bAA, B → b | bs | aBB  

generates strings of terminals that have                        [Paper III June 2012]

(A) odd number of a’s and odd number of b’s

(B) even number of a’s and even number of b’s

(C) equal number of a’s and b’s

(D) not equal number of a’s and b’s

14. The regular expression for the following DFA is      [Paper III June 2012]

(A) ab*(b + aa*b)*           (B) a*b(b + aa*b)*

(C) a*b(b* + aa*b)           (D) a*b(b * + aa*b)*

15. Match the following:                      [Paper III June 2012]

(i) Regular Grammar                           (a) Pushdown automaton

(ii) Context free Grammar                   (b) Linear bounded automaton

(iii) Unrestricted Grammar                  (c) Deterministic finite automaton

(iv) Context Sensitive Grammar          (d) Turing machine

(i)         (ii)        (iii)       (iv)

(A)       (c)        (a)        (b)       (d)

(B)       (c)        (a)        (d)       (b)

(C)       (c)        (b)        (a)       (d)

(D)       (c)        (b)        (d)       (a)

16. Consider the following statements:           [Paper II June 2012]
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true?

(A) I only                    (B) I and II

(C) I and III                (D) II and III

SOLUTIONS

11. D

Strings that are legal according to the given grammar is a, aab, aabab etc

Out of the options the grammar that can produce all these strings is D

Option B seems to be correct in first look, but fails to produce  aab.

12.

13.

14. D

15. B

Grammar Type	Language	machine
Type 0	Recurssively Enumerable/ Un restricted/ Phase structured/ Semithus	Turing Machine
Type 1	Context Sensitive	Linear Bounded Automata
Type 2	Context Free	Pushdown Automata
Type 3	Regular	Finite Automata

16. B

Recursively enumerable languages are closed under the following operations:

• Kleene star L*
• concatenation of L and P
• union of L and P
• intersection L and P.

Recursive languages are closed under the following operations:

• Kleene star L*
• Concatenation L and P
• Union L and P
• Intersection L and P
• Complement of L
• Set difference L - P

So only Statements I and II are true.