Question

Consider the following statements about the context-free grammar
G = {S→ SS, S → ab, S → ba, S→ ϵ }
1. G is a ambiguous.
2. G produces all strings with equal number of a's and b's.
3. G can be accepted by a deterministic PDA
Which combination below expresses all the true statements about G?

Answer 1

G = {S→ SS, S → ab, S → ba, S→ ϵ }
1. "G is ambiguous" is true since ϵ has infinite number of derivations some of which are shown below:

2. "G produces all strings with equal number of a's and b's", is false since $L\left(G\right)=(ab+ba{)}^{\ast }andthislanguage$ cannot produce all strings with equal number of a's and b's. For example aabb has equal number of a's and b's but aabb ∉ L(G).
3."G can be accepted by a DPDA" is true, since L(G) =$(ab+ba{)}^{\ast }andthisisaregularlanguage,$ since we have written a regular expression for it. Since every regular language is also a DCFL, a DPDA exists. which accepts this language.