In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F), a transition of the form, where…

Key idea: the machine pushes one A for every a read, then switches and pops one A for every b read.

Why this describes the accepted language:

• From the start the machine pushes a bottom marker #, then in state q1 it pushes an A on each input a.

• At any point the machine can take an ε-transition to q2 and then for each input b it pops one A.

• A final ε-transition to the accepting state q3 requires the top stack symbol to be A, so acceptance is possible only if at least one A remains on the stack when the input is exhausted.

Therefore the machine accepts exactly the strings of the form a^i b^j with i>j (all a's first, then all b's, and strictly more a's than b's).

Count for length 100:

• If a string has length 100 and is of the form a^i b^j, then i + j = 100 and we require i > j.

• The inequality i > j with i + j = 100 implies i > 50, so i can be any integer from 51 through 100. That gives 100 − 51 + 1 = 50 possible values of i.

Hence the number of length-100 strings accepted by the PDA is 50.