GATE 2021 CS (CS1) – Question 61
In a pushdown automaton $P=(Q,\Sigma,\Gamma,\delta,q_0,F)$, a transition of the form $p \xrightarrow{a, X \to Y} q$ represents $(q,Y)\in\delta(p,a,X)$. Consider the following pushdown automaton over the input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma=\{\#,A\}$: $q_0 \xrightarrow{\epsilon,\epsilon\to\#} q_1$; $q_1$ has a self-loop $a,\epsilon\to A$; $q_1 \xrightarrow{\epsilon,\epsilon\to\epsilon} q_2$; $q_2$ has a self-loop $b,A\to\epsilon$; $q_2 \xrightarrow{\epsilon,A\to A} q_3$ where $q_3$ is the accepting state. The number of strings of length 100 accepted by the above pushdown automaton is ______.

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 50
Explanation
The PDA pushes `#`, then pushes one `A` for each `a` read. It then moves (ε) to $q_2$, where each `b` pops one `A`. The last move to the accepting state $q_3$ is `ε, A → A`: it needs an `A` on top, i.e. at least one `A` must remain.
So accepted strings are $a^nb^m$ with $n\ge1$ and $m<n$.
Length 100: $n+m=100$ and $0\le m<n$, so $m<50$ gives $m=0,1,\dots,49$ (50 values, each with $n=100-m\ge51$).
Number of accepted strings of length 100 $=\mathbf{50}$.