Consider the transition diagram of a PDA given below with input alphabet \(\Sigma = \{a, b\}\) and stack alphabet \(\Gamma = \{X, Z\}\). \(Z\) is the initial stack symbol. Let \(L\) denote the language accepted by the PDA.
Which one of the following is TRUE?
GATE CS - 2016,
Answer: D
The true statement is \(L = \{a^{n} \mid n \ge 0\} \cup \{a^{n}b^{n} \mid n \ge 0\}\) and is deterministic context-free.
The start state is accepting and pushes one X for each a, so any string of a's alone, including the empty string, ends in an accepting state: that gives \(a^{n}\). On the first b the PDA pops an X and moves to the middle state, which pops one X per further b. When the stack is back to Z it takes the \(\varepsilon\) move to the final accepting state. So a's followed by an equal number of b's are accepted: \(a^{n}b^{n}\).
At every point there is at most one move for each combination of state, input and stack top, and the \(\varepsilon\) move on Z does not compete with any input move on Z. The PDA is deterministic, so \(L\) is deterministic context-free, which rules out the option saying no DPDA accepts it. \(L\) is not just \(\{a^{n}b^{n}\}\), since strings like aa are accepted, and every context-free language is decided by some halting Turing machine.
Please log in or register to report this question.
