GATE 2023 CS Q.40: solution and answer

GATE 2023 · CSQ.40 · 2 marks · MCQ

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$ ?

GATE 2023 CS question 40: State diagram with three states s, p, q. — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
${a^{m} b^{n} ∣ 1 \leq m and n < m}$
(B)
${a^{m} b^{n} ∣ 0 \leq n \leq m}$
(C)
${a^{m} b^{n} ∣ 0 \leq m and 0 \leq n}$
(D)
${a^{m} ∣ 0 \leq m} \cup {b^{n} ∣ 0 \leq n}$

Answer and solution

ANSWER

The language accepted by $P$ is ${a^{m} b^{n} ∣ 1 \leq m and n < m}$ , which is option A.

Official answer: ASource: Official answer key, GATE 2023 CS (IIT Kanpur)

In $s$ with $⊥$ on top, the only move is $a /⊥/ A ⊥$ , so the first symbol must be $a$ . The empty string and any string starting with $b$ are rejected, so $m \geq 1$ . This rules out B, C and D, each of which accepts $ε$ .
Reading $m$ a's in $s$ leaves the stack $A^{m} ⊥$ , because each $a / A / AA$ adds one $A$ . No transition outside $s$ reads $a$ , so every $a$ comes before every $b$ .
Path 1: $s \to q$ by $ϵ / A / ϵ$ pops one $A$ and reads no input. State $q$ reads no input, so the remaining input must be empty, which gives $n = 0$ . In $q$ , the loops $ϵ / A / ϵ$ and $ϵ /⊥/ ϵ$ pop the remaining $A$ 's and then $⊥$ . So $a^{m}$ with $m \geq 1$ is accepted.
Path 2: $s \to p$ by $b / A / ϵ$ reads the first $b$ and pops one $A$ . In $p$ , each further $b$ pops one $A$ (loop $b / A / ϵ$ ). After $n \geq 1$ b's, $n$ A's have been popped and $m - n$ remain.
To leave $p$ we need the move $ϵ / A / ϵ$ ( $p \to q$ ), which pops one more $A$ . This needs $m - n \geq 1$ , that is $n < m$ . Then $q$ pops the remaining A's and $⊥$ , so the stack becomes empty.
If $n \geq m$ , the A's run out before $p \to q$ can fire. $⊥$ is then on top, $p$ has no move on $⊥$ , and the stack cannot be emptied, so the string is rejected.
Combining the two paths, the language is ${a^{m} b^{n} ∣ m \geq 1, 0 \leq n < m}$ , which is option A.

KEY IDEA

Acceptance is by empty stack, and the only way to empty it is to get to $q$ . Every $b$ pops an $A$ , and the move into $q$ needs one more $A$ plus input already used up. So at least one $A$ must be left after the b's, which gives $n < m$ .

WATCH OUT FOR

Choosing B ( $n \leq m$ ) by thinking each $b$ simply cancels an $a$ . The exit from $p$ to $q$ pops one extra $A$ , so $n = m$ strands $⊥$ on top. Also forgetting that $ε$ is rejected, since the first move needs an $a$ .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 9 CFG & PDA questions, with notes

GATE 2023 CS Q.40: solution and answer

Answer and solution

More CFG & PDA questions