A machine with memory that grows

w (the remaining input) — it loses symbols from the left as they're read; γ (the stack) changes only via push/pop at its own top, independently.

Yes. It means "change state (and optionally push a symbol) without reading any input and without needing to pop anything" — a pure bookkeeping move, exactly the kind used for the "checkpoint" transitions in this chapter's worked balanced-parentheses design.

One (plus possibly a bottom marker) — same reasoning as G_bal: only one "kind" of matching relationship exists (a against c), so a single running count, implemented as one repeated stack symbol, suffices. b's never touch the stack at all.

The acceptance condition only inspects the final state; but reaching that final state along a legitimate run is only possible if every intermediate move was legal, and pops are only legal when the required symbol is actually on top — so the stack's history is fully "baked into" whether the accepting configuration is reachable at all, without acceptance needing to re-examine it directly.

"(()" processed with a queue: push "(" ,push "(" ,then read ")" — a queue pops from the front (oldest), removing the first "(" pushed rather than the most recent. For this particular single-symbol-type example the immediate effect is invisible (both symbols are identical "(" characters), but the moment two different bracket types are mixed (Problem 6.1.3's multi-type case), a queue would match the wrong bracket to the wrong close, accepting strings like "([)]" that should be rejected.

No explicit "error" rule is needed — if no transition matches (because the required stack symbol isn't there to pop), that branch of computation simply has no move available and dies out. For a nondeterministic PDA this is fine as long as some other branch succeeds; if every branch dies this way, the string is correctly rejected.

The definition only fixes the starting condition (nothing on the stack yet); pushing a marker is simply the very first transition a particular design chooses to take, using the same δ mechanism as every other move — it's a modelling choice made within the formalism, not an exception to it. A design that never needs to detect "stack is otherwise empty" (like a design that only ever checks state, never stack, for acceptance) can skip the marker entirely and still be perfectly valid.

[$] →push→ [$,(] →push→ [$,(,(] →pop→ [$,(] →pop→ [$]. Input exhausted, stack=[$] → checkpoint → accept.

[$]→push a→[$,a]→push a→[$,a,a]→(read first b, switch to q₁, pop)→[$,a]→(read second b, pop)→[$]. Input exhausted, state can reach q_f via the checkpoint → accept.

Push two copies of a marker per a read, or equivalently push once but require two b's to remove it: δ(q₀,a,ε)∋(q₀,a) unchanged, but split the popping into a two-step phase: δ(q₁,b,a)∋(q₂,ε) (half-pop marker), δ(q₂,b,ε)∋(q₁,ε) (second b confirms, no further pop). Simplest fix: push AA for every a, pop one A per b: δ(q₀,a,ε)∋(q₀,AA) if multi-symbol pushes are allowed per move, else chain through an intermediate state.

No. [$] → read ")": need to pop "(" but top is "$" — no matching transition, this branch dies immediately. The only other option at the start is the checkpoint (δ(q_work,ε,$)), which moves to q_accept but still can't handle ")" from there either (q_accept's only move is back to q_work, which then faces the identical dead end). No accepting run exists — correctly rejected.

M_eq has no transition to go back to q₀ (the pushing phase) from q₁ (the popping phase) — once a b is read and the machine moves to q₁, there's no rule for q₁ reading an a at all. "abab" reads a (push, stay q₀), b (pop, move to q₁), then a — and q₁ has no a-transition, so this branch dies. Correctly rejected; no alternating is actually possible.

G_bal allows further balanced groups after an earlier one closes ("()()" is legal), so the machine must be able to keep processing after a checkpoint fires mid-string. L_eq never has anything legal after its own "balanced point" is reached except the end of input — once all a's are matched by b's, any further symbol (of either kind) can only break the required shape, so there's nothing productive for a "resume" move to enable.

Sipser-style transitions can only interact with the stack by popping the required symbol (or nothing) and pushing one symbol (or nothing) — there's no primitive "look without touching." Popping $ and immediately pushing $ back nets to "the stack is unchanged," while still requiring $ to have been on top for the transition to be legal at all — exactly a peek, built from the only two primitives available. The same trick generalises to any design needing "check the stack's current top symbol before deciding what to do next, without actually consuming it" — useful whenever a design wants to react to stack state without spending a real pop on it, such as checking for a language's own bottom-marker before deciding to switch modes elsewhere in a larger machine.

δ(q, id, F) ∋ (q, ε) — read "id", pop F, push nothing (β is empty here, since F→id has no non-terminals after the terminal).

[S] →^{read (, pop S, push SCS} [S,C,S] (S on top) →^{ε, pop S (the →ε rule), push nothing} [C,S] →^{read ), pop C, push nothing} [S] →^{ε, pop S, push nothing} [] — empty stack, input exhausted → accept.

δ(q, id, E) ∋ (q, ε) — identical pattern to 6.3.1, just relabelled: read the terminal, pop the non-terminal, push nothing since there's no β.

Four: A_pp, A_pq, A_qp, A_qq — every ordered pair from {p,q}×{p,q}, matching the general |Q|² count for |Q|=2.

That pattern alone can never introduce an actual terminal symbol into any derivation — splitting a trip into two smaller trips, forever, bottoms out in nothing without the other pattern (A_pq→aA_rsb) providing the base case that actually consumes input. Both patterns are needed: one for "how to combine," one for "what actually happens."

Not as written — the construction specifically exploits "terminal first, then non-terminals" to turn each rule into one clean read-and-replace move. A non-GNF rule (terminal buried in the middle, or multiple terminals) would need converting first (Section 5.1), or a more general (and messier) construction that isn't this section's clean version.

A PDA move reads exactly one input symbol (or none) and replaces exactly one stack symbol with some string. A GNF rule A→aβ reads as exactly one terminal followed by a string of non-terminals — which is precisely "pop A, and whatever comes next in the derivation (β) is what should be pushed, in the same breath as consuming the one terminal a." The two shapes aren't just similar; GNF's defining restriction (terminal first, non-terminals after) is what makes the correspondence a one-line translation instead of requiring any restructuring at construction time — which is exactly why Section 5.1 flagged this use case by name before this section ever arrived.

No. At (q_work, top=$), two moves are available: the checkpoint δ(q_work,ε,$)∋(q_accept,$), and (if more input remains) potentially continuing to push via δ(q_work,(,ε) — an ε-move coexisting with a real-input move at overlapping configurations, exactly the condition Section 6.4's formal definition rules out.

Yes — check each state/top pair: q₀ reading a always pushes and stays; q₀ reading b (with top=a) always switches to q₁; the ε-checkpoint only fires when top=$, never competing with an a/b move (which require top=a). No configuration ever offers two options.

Yes, plausibly — a machine reading a's has no way to know in advance whether it should expect n b's or 2n b's, since both possibilities start identically. This is the same shape of problem as guessing a palindrome's midpoint: the deciding information (which sub-language this string belongs to) isn't available until it's too late to have committed deterministically from the start.

Require an explicit marker after the a's announcing which case applies, e.g. {aⁿ·X·bⁿ} ∪ {aⁿ·Y·b²ⁿ} for two distinct marker symbols X,Y. Reading X or Y deterministically tells the machine which popping rule to use from then on — exactly how "c" removed the guesswork from the palindrome case.

Conflates DCFL with CFL entirely. {ww^R} is context-free (Section 6.4's own nondeterministic PDA recognises it, verified) — it simply isn't in the strictly smaller DCFL class. "Not deterministically recognisable" and "not context-free" are different claims; this chapter's whole point is that they can diverge.

A deterministic machine has exactly one run per input, so "accept" and "reject" are already a clean partition of all possible outcomes — flipping F flips every input's single verdict correctly. A nondeterministic machine can have many runs per input, some accepting and some not; "flip the accept states" doesn't produce "reject exactly the strings that were accepted before," since a string with both an accepting and a non-accepting run would end up accepted both before and after the flip (Section 3.1's exact NFA-complement trap, replayed here for PDAs).

Real call/return checking is deterministic in practice: at any point in execution, the program (or a verifier watching it) knows exactly which function is currently active and exactly which return matches which call — there's no ambiguity to guess through, unlike {ww^R}'s hidden midpoint. This matters enormously for real tooling: a DPDA-shaped problem can be checked in a single deterministic pass, no backtracking, no trying multiple branches — while a genuinely nondeterministic-requiring language would force a checker to explore multiple possibilities (or use a more expensive simulation), exactly the practical cost difference Section 5.4 already hinted at when discussing why grammar shape affects parsing efficiency.

Q (states), Σ (input alphabet), Γ (stack alphabet), δ (transition function), q₀ (start state), F (accepting states).

q = current state, w = remaining (not-yet-read) input, γ = current stack contents, top symbol listed first.

[$]→push→[$,(]→pop→[$]→push→[$,(]→pop→[$]. Stack=[$], input exhausted → checkpoint → accept.

δ(q, a, A) ∋ (q, BC) — read a, pop A, push BC with B ending up on top (leftmost of β on top).

The set of strings that drive the PDA from state p to state q while the stack height returns to exactly where it started, never dropping below that level in between.

Every configuration (state and stack-top combination) has at most one legal move available, across both ε and real-input options combined.

Context-free: yes (a nondeterministic PDA recognises it, Section 6.4). DCFL: no — no deterministic PDA can recognise it, since finding the midpoint deterministically without a marker is impossible.

True — unlike general CFLs (Section 5.3, not closed), a deterministic machine's single verdict per input can be cleanly flipped, the same trick DFAs use.

LIFO (last-in, first-out) — only the most recently pushed symbol is ever available to pop. The classic mistake is treating it like a FIFO queue, which would match symbols in the wrong order the moment more than one symbol type is involved.

Any of: a program's function call/return stack, XML/HTML tag nesting validation, or a network/hardware protocol with nested sessions or transactions — all share the "most recent unfinished thing must close first" LIFO structure a PDA checks natively.