Q6Theory of Computation

$L=\{a^n{b}^{2n}\mid n\ge 1\}$ consists of strings with a block of $n$ a's followed by a block of exactly $2n$ b's. A PDA can recognize this by using the stack to count: push one symbol for each 'a' read, then pop two symbols for every 'b' read (since each 'a' must be matched by two 'b's). The string is accepted if, after consuming all input, the stack is empty (having popped exactly what was pushed) and at least one 'a' was read.

Define the PDA $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$ with $Q=\{q_0,q_1,q_2\}$, $\Sigma =\{a,b\}$, $\Gamma =\{A,Z_0\}$, start state $q_0$, initial stack symbol $Z_0$, and $F=\{q_2\}$ (acceptance by final state, on empty operand stack above $Z_0$). The transitions are:

• $\delta (q_0,a,Z_0)=(q_0,A{Z}_0)$ — push A for the first 'a', replacing $Z_0$ with $A{Z}_0$.
• $\delta (q_0,a,A)=(q_0,AA)$ — push another A for each subsequent 'a'.
• $\delta (q_0,b,A)=(q_1,ϵ)$ — on seeing a 'b', pop the top A (this is the first of the two b's assigned to that A) and move to state $q_1$.
• $\delta (q_1,b,A)=(q_0,A)$ — on seeing the second 'b' for the same A, leave the stack unchanged and return to $q_0$, ready for the next A's pair of b's (or end of input).
• $\delta (q_0,ϵ,Z_0)=(q_2,Z_0)$ — if the stack is back to just $Z_0$ (all A's popped) and input is exhausted, move to the accepting state $q_2$.

For input $aabbbb$ ($n=2$, so $2n=4$ b's are expected): start $(q_0,aabbbb,Z_0)$. Read 'a': push A, giving $(q_0,abbbb,A{Z}_0)$. Read 'a': push A again, giving $(q_0,bbbb,AA{Z}_0)$. Now each A on the stack must absorb exactly two b's via the $q_0\to q_1\to q_0$ toggle. Read first 'b': pop the top A, move to $q_1$: $(q_1,bbb,A{Z}_0)$. Read second 'b': this second b for the same A returns control to $q_0$ without popping further (the toggle only pops on entry to $q_1$), giving $(q_0,bb,A{Z}_0)$. Read third 'b': pop the remaining A, move to $q_1$: $(q_1,b,Z_0)$. Read fourth 'b': return to $q_0$: $(q_0,ϵ,Z_0)$. Input is now empty and the stack holds only $Z_0$, so $\delta (q_0,ϵ,Z_0)$ fires, moving to $q_2\in F$, and $aabbbb$ is accepted.

The stack height after reading the a-block equals $n$ (the number of a's), and each $q_0\to q_1\to q_0$ toggle consumes exactly two b's while popping exactly one A, so the machine can consume exactly $2n$ b's before the stack returns to bare $Z_0$; reading more or fewer b's leaves either a non-empty stack of A's (input exhausted with no $ϵ$-move to $q_2$ possible, since that move requires $Z_0$ on top) or an empty stack while b's remain unconsumed (no valid transition, since $q_0$ on $Z_0$ has no move on 'b'), so the PDA accepts $w$ if and only if $w=a^n{b}^{2n}$ for some $n\ge 1$. This PDA has one stack symbol type per counted quantity, illustrating the general technique for context-free languages defined by a fixed integer ratio between two blocks of symbols, and confirms via the pushdown-automata/context-free-grammar equivalence that $L$ is context-free, matching the grammar $S\to aSbb\mid abb$.