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. 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$ for each `a` (so $m\ge1$) and must leave the first phase with an $\varepsilon$-move that pops an $A$. The `b`'s then pop at most the remaining $m-1$ $A$'s, so $n<m$, and the final $\varepsilon$-moves empty the stack.