GATE CS 2016 Set 1 Q43 — Context-free Grammars and Push-down Automata

To determine which option is correct, let us analyze the language $L$ accepted by the given Pushdown Automaton (PDA) and its properties:

1. Language Identification: The PDA pushes $X$ onto the stack for every input symbol $a$. While reading $a$'s, the machine remains in accepting states, which accepts the language $L_1 = \{a^n \mid n \geq 0\}$. If a $b$ is encountered, the PDA transitions to a state where it pops $X$ from the stack for each $b$. It accepts at the end of the input if the stack is emptied back to the initial symbol $Z$. This matches the number of $b$'s with $a$'s, accepting the language $L_2 = \{a^n b^n \mid n \geq 0\}$. Thus, the total language accepted is $L = L_1 \cup L_2 = \{a^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$.
2. Determinism: A Deterministic PDA (DPDA) can easily decide this language. While reading $a$'s, the DPDA stays in an accepting state. If the input ends, it accepts $a^n$. If a $b$ appears, it uniquely transitions to a popping state to match the count. Since there are no overlapping transitions (no choice between reading $a$ or $b$, or making $\epsilon$-transitions), the machine is completely deterministic.

Therefore, $L$ is a deterministic context-free language (DCFL), which makes option D the correct statement.