GATE CS 2003 Q51 — Context-free Grammars and Push-down Automata

The given grammar is:

This grammar generates the language $L(G)$ of balanced parentheses (often called the Dyck language $D_1$), where $a$ represents the opening parenthesis and $b$ represents the closing parenthesis.

Let's analyze each option:

• Option A: $G$ is not ambiguous
  The grammar is highly ambiguous. For example, the string $\epsilon$ has multiple derivations:
  1. $S \Rightarrow \epsilon$
  2. $S \Rightarrow SS \Rightarrow \epsilon\epsilon = \epsilon$
  Hence, $G$ is ambiguous. This statement is false.
• Option B: There exist $x, y \in L(G)$ such that $xy \notin L(G)$
  Since the grammar contains the rule $S \to SS$, if $x \in L(G)$ and $y \in L(G)$, we can derive $xy$ starting from $S$ via $S \to SS \Rightarrow^* xy$. Thus, $L(G)$ is closed under concatenation, meaning $xy \in L(G)$ for all $x, y \in L(G)$. This statement is false.
• Option C: There is a deterministic pushdown automaton that accepts $L(G)$
  The language of balanced parentheses is a well-known Deterministic Context-Free Language (DCFL). A Deterministic PDA (DPDA) can accept it by pushing $a$ onto the stack and popping $a$ when $b$ is encountered. If the stack is empty at the end of the input, the string is accepted. This statement is true.
• Option D: We can find a deterministic finite state automaton that accepts $L(G)$
  The language $L(G)$ requires matching an arbitrary number of nested $a$'s and $b$'s, which requires infinite memory. Since it is not a regular language, no DFA can accept it. This statement is false.