The GATE Grind

GATE 2023 CS – Question 40

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

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?

Diagram for GATE 2023 CS question 40
  1. $\{a^m b^n \mid 1 \le m \text{ and } n < m\}$
  2. $\{a^m b^n \mid 0 \le n \le m\}$
  3. $\{a^m b^n \mid 0 \le m \text{ and } 0 \le n\}$
  4. $\{a^m \mid 0 \le m\} \cup \{b^n \mid 0 \le n\}$

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.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →