GATE CS 2006 Q32 — Parsing (LL, LR)

To determine the correct statement(s), let us analyze each statement individually:

Statement I: $G$ is ambiguous

• A grammar is ambiguous if there exists at least one string in its language that has more than one leftmost derivation (or parse tree).
• Consider the string $w = ab$. We can derive it in multiple ways:
  • Derivation 1: $S \rightarrow ab$
  • Derivation 2: $S \rightarrow SS \rightarrow ab S \rightarrow ab \epsilon = ab$
• Since the string $ab$ has multiple distinct leftmost derivations, the grammar $G$ is ambiguous. Thus, Statement I is TRUE.

Statement II: $G$ produces all strings with equal number of $a$’s and $b$’s

• The production rules of $G$ are $S \rightarrow SS \mid ab \mid ba \mid \epsilon$.
• Every non-empty terminal string generated by this grammar must be formed by concatenating the blocks $ab$ and $ba$. Thus, the language generated is $L(G) = (ab \mid ba)^*$.
• Consider the string $w = aabb$. It has an equal number of $a$'s and $b$'s, but it cannot be generated by $G$ because any string in $L(G)$ must start with either $ab$ or $ba$.
• Since $aabb \notin L(G)$, Statement II is FALSE.

Statement III: $G$ can be accepted by a deterministic PDA

• The language $L(G) = (ab \mid ba)^*$ is a regular language because it can be represented by a regular expression.
• Every regular language can be accepted by a Deterministic Finite Automaton (DFA).
• Since any language accepted by a DFA can also be accepted by a Deterministic Pushdown Automaton (DPDA) by simply not using the stack, $L(G)$ is accepted by a deterministic PDA. Thus, Statement III is TRUE.

Therefore, only statements I and III are true.