The GATE Grind

GATE 2021 CS (CS1) – Question 61

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Numerical answer

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 ______.

Diagram for GATE 2021 CS (CS1) question 61

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}$.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →