GATE 2023 CS – Question 40
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {⊥, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/γ, where c is an input symbol or ε, X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v. In the initial configuration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack. [Figure: s has transitions a/⊥/A⊥ and a/A/AA; then ε/A/ε moves to p; p has b/A/ε; q has ε/A/ε and ε/⊥/ε.] Which one of the following options correctly describes the language accepted by P?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $\{a^m b^n \mid 1 \le m \text{ and } n < m\}$
Explanation
The PDA pushes one A per a (m ≥ 1) and must leave the first-phase state with an ε-move that pops an A. The b's then pop at most the remaining m−1 A's, so n < m, and the final ε-moves empty the stack.