GATE 2021 CS – 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 ______.