Question

In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F) over Σ={a,b}, Γ={#,A}: q0 (start) moves to q1 via ε,ε→# (push the bottom marker). q1 has a self-loop on a,ε→A (push A for each 'a', regardless of current top). q1 moves to q2 via ε,ε→ε (a spontaneous, nondeterministic switch). q2 has a self-loop on b,A→ε (pop an A for each 'b'). q2 moves to the sole accepting state q3 via ε,A→A (a spontaneous move requiring the top of stack to currently be A). The number of strings of length 100 accepted by this pushdown automaton is ____.

Accepted Answer

The correct answer is 50. The machine pushes one A per 'a' read in q1, then (after a nondeterministic switch to q2) pops one A per 'b' read. To reach the accepting state q3, the final ε-move requires the stack top to still be A — meaning strictly fewer b's were read than a's (at least one A must remain unpopped). So the accepted language is {aⁱbʲ : i > j ≥ 0}. For total length i+j=100 with j50 ⟹ i≥51 (checking i=50,j=50 fails since j

Explanation