Consider the following statements about the context free grammar G = {S → SS,…
2006
Consider the following statements about the context free grammar
G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
- A.
I only
- B.
I and III only
- C.
II and III only
- D.
I, II and III
Attempted by 12 students.
Show answer & explanation
Correct answer: B
Key observation: the grammar's productions produce exactly concatenations of "ab" and "ba" (including the empty string).
In formal terms: L(G) = (ab | ba)*.
Why the grammar is ambiguous: any string formed by three or more blocks of "ab"/"ba" can be parsed with different binary tree associations (different parenthesizations). For example, the string "ababab" can come from ((ab)(ab))(ab) or (ab)((ab)(ab)), giving distinct parse trees.
Why the grammar does not generate all strings with equal numbers of a and b: equality of counts is necessary but not sufficient. A counterexample is "aabb" (two a's followed by two b's): it has equal counts but cannot be written as a concatenation of "ab" and "ba" blocks, so it is not in L(G).
Why the language is accepted by a deterministic PDA: since L(G) is regular (it equals (ab|ba)*), it can be recognized by a DFA, and every DFA can be simulated by a deterministic PDA. Therefore a deterministic PDA exists that accepts L(G).
Conclusion: the true statements are that the grammar is ambiguous and that it can be accepted by a deterministic PDA. The statement that it generates all strings with equal numbers of a and b is false.
Final answer: I and III only.
A video solution is available for this question — log in and enroll to watch it.