GATE CS 2021 Set 1 Q51 — Context-free Grammars and Push-down Automata

By analyzing the transitions of the given pushdown automaton (PDA), we can determine the language it accepts:

1. State $q_0$ (Push Phase): For every symbol $a$ read, an $A$ is pushed onto the stack. Thus, reading $a^n$ (where $n \ge 1$) results in $n$ $A$'s on the stack above the initial symbol $\#$.
2. State $q_1$ (Pop Phase): The transition from $q_0$ to $q_1$ occurs on the first $b$, popping one $A$. Subsequent $b$'s are read in $q_1$, each popping one $A$. If $m$ $b$'s are read in total ($m \ge 1$), then $m$ $A$'s are popped.
3. State $q_2$ (Acceptance Phase): The PDA transitions to the final state $q_2$ on $\epsilon$ input if:
   • The stack has only $\#$ left (i.e., $n = m$), via transition $\epsilon, \# / \#$.
   • The stack still has $A$'s left (i.e., $n > m$), via transition $\epsilon, A / A$.

Thus, the language accepted by the PDA is:

We need to find the number of strings in $L$ of length $100$:

Substituting $n = 100 - m$ into the inequality:

Since $m \ge 1$, the possible integer values for $m$ are:

Each value of $m$ uniquely determines $n = 100 - m$. Therefore, there are exactly 50 such strings.