GATE CS 2023 Q30 — Context-free Grammars and Push-down Automata

To find the language accepted by the PDA $P$ by empty stack, let us trace the transitions step-by-step:

• State $s$ (Pushing $A$'s): The self-loops on state $s$ are $a, \perp / A\perp$ and $a, A / AA$. This means for every input symbol $a$, one $A$ is pushed onto the stack. To push any $A$ and proceed, we must read at least one $a$, so $m \ge 1$. After reading $a^m$, the stack contains $A^m \perp$.
• Transition to state $p$ (Reading $b$'s): The transition from $s$ to $p$ is $b, A / \epsilon$, and the self-loop on $p$ is $b, A / \epsilon$. This means we must read at least one $b$ to leave state $s$, which implies $n \ge 1$. Each $b$ read pops one $A$ from the stack. After reading $b^n$, the stack has $A^{m-n} \perp$.
• Transition to state $q$ (Emptying the stack): The transition from $p$ to $q$ is $\epsilon, A / \epsilon$. This is an $\epsilon$-transition that pops an $A$ without consuming any input. For this transition to be valid, there must be at least one $A$ remaining on the stack after reading all $b$'s. This requires: $$m - n \ge 1 \implies n < m$$
• State $q$: Once in state $q$, the self-loop $\epsilon, A / \epsilon$ pops any remaining $A$'s, and the transition $\epsilon, \perp / \epsilon$ pops the bottom-of-stack marker $\perp$, emptying the stack and accepting the string.

Combining these conditions, we get $1 \le m$ and $n < m$. Thus, the accepted language is:

$\left\{a^{m} b^{n} \mid 1 \leq m \text{ and } n < m\right\}$