GATE CS 2023 Q.40: Context-Free Grammars, Pushdown Automata and CFLs

Consider the pushdown automaton (PDA) P below, which runs on the input alphabet $\{a, b\}$ , has stack alphabet $\{\bot, 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/\gamma$ , where $c$ is an input symbol or $\epsilon$ , $X$ is a stack symbol, and $\gamma$ 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 $\gamma$ on the stack, and go to state $v$ . In the initial configuration, the stack has only the symbol $\bot$ in it. The PDA accepts by empty stack.

Pushdown automaton P with states {s, p, q}, start state s, self-loop on s for a/bottom/A bottom and a/A/AA, transition s->p on b/A/epsilon, self-loop on p for b/A/epsilon, transitions s->q and p->q on epsilon/A/epsilon, and self-loop on q for epsilon/A/epsilon and epsilon/bottom/epsilon.

Which one of the following options correctly describes the language accepted by P?

$\{a^m b^n \mid 1 \le m \text{ and } n < m\}$

$\{a^m b^n \mid 0 \le n \le m\}$

$\{a^m b^n \mid 0 \le m \text{ and } 0 \le n\}$

$\{a^m \mid 0 \le m\} \cup \{b^n \mid 0 \le n\}$

Official answer and solution

Official answer: A
From: Official GATE 2023 answer key

Solution

Trace stack pushes and pops for inputs $a$ and $b$ to determine the condition for empty-stack acceptance.

The start state is $s$ with initial stack $\bot$ .
On reading input $a$ $a$ :
- First $a$ : transition $a/\bot/A\bot$ pushes $A$ on top of $\bot$ .
- Subsequent $a$ 's: self-loop $a/A/AA$ pushes another $A$ for each $a$ .
  So after reading $a^m$ ( $m \ge 1$ ), the stack contains $A^m \bot$ .
On reading input $b$ $b$ :
- The PDA moves from $s$ to state $p$ via $b/A/\epsilon$ (consuming one $b$ and popping one $A$ ).
- Further $b$ 's loop at $p$ via $b/A/\epsilon$ , each consuming a $b$ and popping an $A$ .
  So after reading $b^n$ , the stack contains $A^{m-n} \bot$ .
To reach empty stack:
- From $s$ or $p$ , the PDA transitions on $\epsilon/A/\epsilon$ to state $q$ (requiring at least one $A$ to be left on the stack when switching to $q$ , meaning $m > n$ ).
- At state $q$ , the PDA pops all remaining $A$ 's via $\epsilon/A/\epsilon$ and finally pops $\bot$ via $\epsilon/\bot/\epsilon$ , leaving the stack empty.
Therefore, the PDA requires at least one $a$ ( $m \ge 1$ ) and strictly fewer $b$ 's than $a$ 's ( $n < m$ ).

Thus, $L = \{a^m b^n \mid 1 \le m \text{ and } n < m\}$ .

Final answer

Option (A)

Common trap

Allowing $n = m$ , which prevents the $\epsilon/A/\epsilon$ transition to $q$ because no $A$ would remain to trigger it.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 40 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source