Automata Theory

Theory of computation

Multiple Choice Questions (Set I)

In each of the following questions, choose the correct answer from the four choices provided.

1.	The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c is is type 3 is type 2 but not type 3 is type 1 but not type 2 is type 0 but not type 1
2.	The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → bc is is type 3 is type 2 but not type 3 is type 1 but not type 2 is type 0 but not type 1
3.	The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a is is type 3 is type 2 but not type 3 is type 1 but not type 2 is type 0 but not type 1
4.	The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = (a, b, c} P : S → ABCD BCD → DE D → aD D → a E → bE E → c is is type 3 is type 2 but not type 3 is type 1 but not type 2 is type 0 but not type 1
5.	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 leftmost derivation a rightmost derivation both leftmost and rightmost derivation neither leftmost nor rightmost derivation
6.	Consider the following language L = {anbncndn|n ≥ 1} L is CFL but not regular CSL but not CFL regular type 0 language but not type 1
7.	Consider the following language L = {anbn|n ≥ 1} L is CFL but not regular CSL but not CFL regular type 0 language but not type 1
8.	Consider the following language L = {anbmcpdq|n, m, p, q ≥ 1} L is CFL but not regular CSL but not CFL regular type 0 language but not type 1
9.	The following CFG is in S → AB B → CD B → AD B → b D → AD D → d A → a C → a Chomsky normal form but not strong Chomsky normal form Weak Chomsky normal form but not Chomsky normal form Strong Chomsky normal form Greibach normal form
10.	The following CFG is in S → aBB B → bAA A → a B → b Chomsky normal form but not strong Chomsky normal form Weak Chomsky normal form but not Chomsky normal form Strong Chomsky normal form Greibach normal form
	Answers 1. b 2. c 3. a 4. d 5. d 6. b 7. a 8. c 9. c 10. d Next