Exercises — Pushdown automata (PDA) — configuration, acceptance by empty stack - final state

(a) False. The configuration $(q,w,\gamma )$ stores only the remaining unread input $w$. Already-read input cannot affect the future, so it is deliberately dropped. (b) True. $L_N(M)=\{w\mid (q_0,w,Z_0){⊢}^{\ast }(q,\epsilon ,\epsilon )\}$ — the condition is "stack empty," not "state in $F$." (c) False. By convention the top is leftmost. In $A\beta$, symbol $A$ is on top and $\beta$ is the tail below it.

$\delta$ must return a finite set of pairs $(\text{state},\text{string of stack symbols})$. (a) Valid — a set with one pair $(q,A{Z}_0)$. (b) Invalid — it is a bare pair, not a set. Correct form: $\{(q,AA)\}$. (c) Valid — two pairs (nondeterministic choice: pop, or leave one $A$). (d) Invalid — $\{q\}$ is a set of states, missing the pushed string.

Rules: (1) $\delta (q,a,Z_0)=\{(q,A{Z}_0)\}$, (2) $\delta (q,a,A)=\{(q,AA)\}$, (3) $\delta (q,b,A)=\{(q,\epsilon )\}$, (4) $\delta (q,\epsilon ,Z_0)=\{(q,\epsilon )\}$. Each step names the rule that fires and why it is the only legal one. $(q,aaabbb,Z_0)\underset{\text{(1) read }a,\text{top }{Z}_0\text{: push }A}{⊢}(q,aabbb,A{Z}_0)\underset{\text{(2) read }a,\text{top }A\text{: push }A}{⊢}(q,abbb,AA{Z}_0)$ $\underset{\text{(2) read }a,\text{top }A\text{: push }A}{⊢}(q,bbb,AAA{Z}_0)\underset{\text{(3) read }b,\text{top }A\text{: pop}}{⊢}(q,bb,AA{Z}_0)\underset{\text{(3) read }b\text{: pop}}{⊢}(q,b,A{Z}_0)$ $\underset{\text{(3) read }b\text{: pop last }A}{⊢}(q,\epsilon ,Z_0)\underset{\text{(4) }\epsilon \text{-move, top }{Z}_0\text{: pop marker}}{⊢}(q,\epsilon ,\epsilon )✓$ Why each is forced: with top $Z_0$ and next input $a$, only rule 1 applies; with top $A$ and next $a$, only rule 2; with top $A$ and next $b$, only rule 3; with input exhausted and top $Z_0$, only rule 4. Stack empty, input fully read ⇒ accepted. The maximum stack height was $4$ (the three $A$'s plus $Z_0$).

Accepting run on $aabb$ (each ⊢ labelled with the firing rule): $(q,aabb,Z_0)\underset{\text{(1) push }A}{⊢}(q,abb,A{Z}_0)\underset{\text{(2) push }A}{⊢}(q,bb,AA{Z}_0)\underset{\text{(3) pop}}{⊢}(q,b,A{Z}_0)$ $\underset{\text{(3) pop last }A}{⊢}(q,\epsilon ,Z_0)\underset{\text{(4’) }\epsilon \text{-move, top }{Z}_0\text{: go to }{q}_f}{⊢}(q_f,\epsilon ,Z_0)✓$ $q_f\in F$ and input is exhausted ⇒ accept (stack still holds $Z_0$, which is fine — final-state mode ignores the stack).

Rejecting $abb$: $(q,abb,Z_0)\underset{\text{(1) push }A}{⊢}(q,bb,A{Z}_0)\underset{\text{(3) pop}}{⊢}(q,b,Z_0)$ Now we are in state $q$ with unread input $b$ and top $Z_0$. There is no rule $\delta (q,b,Z_0)$ (rule 4' needs $\epsilon$-input, not $b$) — the machine is stuck with input remaining. It never reaches $q_f$ having read all input, so $abb\notin L_F$. Correct: $abb$ has one $a$ but two $b$'s. ✓

Idea: each $a$ pushes two $A$'s (so we owe two $b$'s per $a$); each $b$ pops one $A$. Label each ⊢: $(q,aabbbb,Z_0)\underset{a,\text{top }{Z}_0:\text{push }AA}{⊢}(q,abbbb,AA{Z}_0)\underset{a,\text{top }A:\text{push }AA}{⊢}(q,bbbb,AAAA{Z}_0)$ $\underset{b:\text{pop}}{⊢}(q,bbb,AAA{Z}_0)\underset{b:\text{pop}}{⊢}(q,bb,AA{Z}_0)\underset{b:\text{pop}}{⊢}(q,b,A{Z}_0)\underset{b:\text{pop last }A}{⊢}(q,\epsilon ,Z_0)\underset{\epsilon ,\text{top }{Z}_0:\text{pop marker}}{⊢}(q,\epsilon ,\epsilon )✓$ Two $a$'s pushed $4$ $A$'s; four $b$'s popped all $4$; marker-pop empties the stack. The design is correct. Max stack height reached: $5$ ($AAAA$ + $Z_0$). Check the guard: a bad string like $aab$ would push $AAAA$ then pop once on the single $b$, leaving $(q,\epsilon ,AAA{Z}_0)$ — non-empty, no more moves, rejected, as required.

Start configuration on empty input: $(q,\epsilon ,Z_0)$. Rule 4 ($\delta (q,\epsilon ,Z_0)=\{(q,\epsilon )\}$) applies immediately, because its $\epsilon$-input needs no letter and its required top $Z_0$ is present: $(q,\epsilon ,Z_0)\underset{\text{(4) }\epsilon \text{-move: pop }{Z}_0}{⊢}(q,\epsilon ,\epsilon )✓$ The stack empties with no input consumed, so $\epsilon$ is accepted. But $\epsilon =a^0{b}^0$ has $n=0$, which our language $\{a^n{b}^n\mid n\ge 1\}$ excludes. So this PDA actually recognises $\{a^n{b}^n\mid n\ge 0\}$. To exclude $\epsilon$ you must force at least one $a$ before the marker can be popped — e.g. only allow the marker-pop from a distinct "seen-a-then-b" state.

Since $i=j+k$, every $a$ must be cancelled by exactly one later symbol ($b$ or $c$). Push one $A$ per $a$; pop one $A$ per $b$, then one $A$ per $c$. Use states to enforce the order $a^{\ast }{b}^{\ast }{c}^{\ast }$. States $\{q_a,q_b,q_c\}$, start $q_a$, stack alphabet $\{A,Z_0\}$.

• $\delta (q_a,a,Z_0)=\{(q_a,A{Z}_0)\}$, $\delta (q_a,a,A)=\{(q_a,AA)\}$ — push per $a$.
• $\delta (q_a,\epsilon ,Z_0)=\{(q_a,\epsilon )\}$ — the $i=0$ escape (see WHY below).
• $\delta (q_a,b,A)=\{(q_b,\epsilon )\}$, $\delta (q_b,b,A)=\{(q_b,\epsilon )\}$ — pop per $b$, lock into $b$-phase.
• $\delta (q_a,c,A)=\{(q_c,\epsilon )\}$, $\delta (q_b,c,A)=\{(q_c,\epsilon )\}$, $\delta (q_c,c,A)=\{(q_c,\epsilon )\}$ — pop per $c$.
• $\delta (q_b,\epsilon ,Z_0)=\{(q_b,\epsilon )\}$, $\delta (q_c,\epsilon ,Z_0)=\{(q_c,\epsilon )\}$ — pop marker when all $A$'s gone ⇒ empty stack.

WHY the $\delta (q_a,\epsilon ,Z_0)=\{(q_a,\epsilon )\}$ rule does not misfire: its required top is $Z_0$, which — in state $q_a$ — is only exposed in two situations: (i) at the very start before any $a$ is read, or (ii) never again once an $a$ has pushed an $A$, because from then on the top is $A$ (not $Z_0$) until every $A$ is popped, and popping $A$'s can only happen in states $q_b$ or $q_c$, never back in $q_a$. So in state $q_a$ the marker is re-exposed only on the truly empty input. That is exactly the $i=0,j=0,k=0$ case (the empty string, which satisfies $i=j+k$), so accepting it is correct, and it cannot "eat" the marker in the middle of a real $a^i{b}^j{c}^k$ string. The order-enforcing states help here too: once we leave $q_a$ we never return, so this rule is inert during the $b$- and $c$-phases.

Why it works overall: total pops $=j+k$; total pushes $=i$. The stack empties (after the marker pop) iff $i=j+k$. Ordering states guarantee $a$'s precede $b$'s precede $c$'s. Test $aabc$ ($i=2,j=1,k=1$): push $AA$, pop on $b$, pop on $c$, pop $Z_0$ ⇒ empty ⇒ accept. ✓ Test $aaabc$ ($i=3,j=1,k=1$): $j+k=2\ne 3$, so after $aaabc$ one leftover $A$ remains on the stack ⇒ not empty ⇒ rejected. ✓

What "fresh $X_0$" means and how it differs from $Z_0$: $Z_0$ is the old machine's bottom marker — the symbol whose disappearance signalled "stack empty ⇒ accept." $X_0$ is a brand-new symbol added to $\Gamma$ that appears in no old rule (that is what "fresh" means: it is not used anywhere else, so no existing transition can touch it). We place $X_0$ below $Z_0$ as the true bottom. Now $Z_0$ is no longer the bottom — it is an ordinary symbol the old rules manipulate, while $X_0$ sits underneath, guaranteeing the stack is never physically empty during simulation.

Construction. Add a fresh start state $p_0$ and a fresh final state $q_f$.

• New start: $p_0$, new initial stack symbol $X_0$.
• $\delta (p_0,\epsilon ,X_0)=\{(q,Z_0{X}_0)\}$ — push the old start symbol $Z_0$ above $X_0$, jump to old start state $q$.
• Keep old rules 1–3 unchanged.
• Replace old rule 4 with $\delta (q,\epsilon ,Z_0)=\{(q,\epsilon )\}$ (pop $Z_0$, exactly as the old machine emptied), then
• $\delta (q,\epsilon ,X_0)=\{(q_f,X_0)\}$ — when the fresh marker $X_0$ finally surfaces, go to final state $q_f$.
• $F=\{q_f\}$.

WHY the freshness matters: the old machine accepted precisely by reaching a physically empty stack. If we only bolted on a final state without $X_0$, then (a) at the accept moment there would be no top symbol left to trigger the $\epsilon$-move into $q_f$, and (b) any partial run that emptied the stack early could be misinterpreted. Because $X_0$ is fresh (untouched by old rules) and sits at the very bottom, the only moment $X_0$ is ever exposed is exactly when the old run would have emptied — no sooner. So $L_F(\text{new})=L_N(\text{old})=\{a^n{b}^n\}$.

States $\{q_1,q_2\}$ (push phase, pop phase), stack $\{a,b,Z_0\}$.

• Push phase: $\delta (q_1,x,Y)=\{(q_1,xY)\}$ for $x\in \{a,b\}$, any top $Y$ — push each read symbol.
• Guess midpoint: $\delta (q_1,\epsilon ,Y)=\{(q_2,Y)\}$ — nondeterministically switch to popping.
• Pop phase: $\delta (q_2,x,x)=\{(q_2,\epsilon )\}$ — pop only if top equals current input (match).
• $\delta (q_2,\epsilon ,Z_0)=\{(q_2,\epsilon )\}$ — empty the marker ⇒ accept.

Accepting branch on $abba$ (guess midpoint after 2 symbols), each ⊢ labelled: $(q_1,abba,Z_0)\underset{\text{push }a}{⊢}(q_1,bba,a{Z}_0)\underset{\text{push }b}{⊢}(q_1,ba,ba{Z}_0)\underset{\epsilon :\text{guess mid, go }{q}_2}{⊢}(q_2,ba,ba{Z}_0)$ $\underset{\text{top }b=\text{input }b:\text{pop}}{⊢}(q_2,a,a{Z}_0)\underset{\text{top }a=\text{input }a:\text{pop}}{⊢}(q_2,\epsilon ,Z_0)\underset{\epsilon ,\text{top }{Z}_0:\text{pop marker}}{⊢}(q_2,\epsilon ,\epsilon )✓$ Dying branch (guess midpoint too early, after 1 symbol): $(q_1,abba,Z_0)\underset{\text{push }a}{⊢}(q_1,bba,a{Z}_0)\underset{\epsilon :\text{guess mid too early}}{⊢}(q_2,bba,a{Z}_0)$ Now top is $a$ but next input is $b$; the pop rule $\delta (q_2,x,x)$ requires top equal to the input, and $a\ne b$, so no rule $\delta (q_2,b,a)$ exists ⇒ this branch is stuck with input left and dies. Since acceptance requires some branch to succeed, and the correct-midpoint branch does, $abba\in L$.

Reading the figure below. It draws these two branches side by side: the shared push of the first $a$ at the top, then the split. The left (orange) path guesses the midpoint after exactly two symbols and walks all the way down to $(q_2,\epsilon ,\epsilon )$ — accept. The right (plum) path guesses one symbol too early; its next required pop compares top $a$ against input $b$, finds no matching rule, and terminates (labelled "DIES"). The picture makes visible why the guess must land on the true centre: only then do the popped symbols line up with the remaining input.

First, the precise constraints that define a DPDA (these are the formal WHY):

1. Single-move restriction: for every triple $(q,a,A)$ with $a\in \Sigma$, $|\delta (q,a,A)|\le 1$ — at most one legal move. There is no set of alternatives to explore.
2. No competing $\epsilon$-move: if $\delta (q,\epsilon ,A)\ne \varnothing$ then $\delta (q,a,A)=\varnothing$ for every input symbol $a$. So a DPDA can never choose between "read a letter" and "make a silent move" on the same top symbol.
3. One-symbol window: a single move sees only the next one input symbol and the single top-of-stack symbol — no lookahead further into the input.

Consequence for $w{w}^R$: to recognise it the machine must flip from pushing the first half to matching the second half exactly at the midpoint. But the midpoint is unmarked: reading $abba$, after ab the machine cannot tell whether it stands at the true centre or is still inside the first half (the string could equally have continued as $abab\dots$). Constraint 3 forbids peeking ahead to resolve this; constraints 1–2 forbid trying both possibilities. So a DPDA is forced to commit to one guess with a single deterministic path — and for the family of strings where the centre is genuinely ambiguous, whichever it commits to is wrong on some input.

A nondeterministic PDA escapes precisely because it is allowed multiple moves (its $\delta$ may return a set): Exercise 5.1's $\epsilon$-move $\delta (q_1,\epsilon ,Y)=\{(q_2,Y)\}$ coexists with the push move on the same top symbol, letting it split off a "guess the midpoint here" branch at every position at once. One branch guesses correctly and accepts. Because a DPDA cannot make that guess, $\{w{w}^R\}$ separates the classes: it is a language of PDAs but not of DPDAs, proving DPDA ⊊ PDA. This is unlike finite automata, where the subset construction (Nondeterministic Finite Automata) makes DFA = NFA — the stack blocks that trick. Compare with Context-Free Grammars: every CFL has some PDA, but not necessarily a deterministic one.

L1: top of stack is written where in $\gamma$? ::: Leftmost. L2: does final-state acceptance require an empty stack? ::: No — it ignores stack contents. L3: what accidental string does a bare $\epsilon$-marker-pop accept? ::: $\epsilon$ (empty string). L4: what does the fresh marker $X_0$ prevent in empty→final conversion? ::: Accidental early emptying / false accept (and it gives a top symbol to trigger the accept move). L5: why can't a DPDA do $w{w}^R$? ::: It cannot guess the unmarked midpoint (single move, no competing $\epsilon$-move, one-symbol window).