Every grammar, one predictable shape

Both yes. X₁→A_plusT is A→BC (two non-terminals). F→id is A→a (one terminal, since "id" is treated as a single atomic terminal symbol).

TERM: A_a→a, A_b→b, giving S→A_aSA_b | A_aA_b. BIN: S→A_aX, X→SA_b. Final: S→A_aX | A_aA_b; X→SA_b; A_a→a; A_b→b. (No UNIT or DEL step needed — no unit or ε rules existed to begin with.)

It still needs the same substitution: S→AB starts with a non-terminal, so it must become S→aAB|aB exactly as before. Only B's own rule changed (B→b instead of B→bB|b), which doesn't affect whether S needs fixing.

Because S₀→E was itself a unit rule, and the UNIT-removal step for S₀ copies all of E's (already non-unit) rules directly — S₀'s unit-closure is exactly {S₀,E,T,F}, the same closure E itself sits inside, so they end up with identical rule sets, differing only in name.

Dropping F breaks the grammar — X₂→A_starF still directly names F on its right side, and X₂ is reachable (via T→TX₂). UNIT-removal copies a target's rules upward to whoever pointed at it via a unit rule; it never deletes the target itself if something else still legitimately needs it.

No. Since L(CNF version) = L(original) exactly, the count of length-n strings in the language is identical before and after — only the internal machinery (number of non-terminals, rule shapes, even the parse tree's exact shape) changes, never the language itself or anything derived purely from the language.

UNIT-removal only ever copies rules along unit chains (A→B, one non-terminal to another), and a grammar has only finitely many non-terminals, so the unit-closure computation (Section 5.1) always terminates — there's no way to "regenerate the same problem." GNF substitution, though, replaces a leading non-terminal with all of its right-hand sides, including ones that might start with the very same non-terminal being substituted (that's exactly what left recursion is) — so a naive substitution can reintroduce the identical leading non-terminal it just tried to remove, forever. That's precisely why left-recursion elimination has to happen as a separate, prior step.

With branching factor exactly 2, a tree with n leaves must have height at least log₂n — more leaves forces a taller tree, and a tall enough tree has a root-to-leaf path longer than the number of available non-terminals, forcing pigeonhole to bite along that specific path.

u="a", v="aa" (from the remaining a's, |vxy|=2≤3), x="", y="" (or fold whatever remains appropriately) — concretely u=ε, v=aa, x=a, y=ε, z=b³c³ works: |vxy|=3≤p, |vy|=2>0. At i=0: uv⁰xy⁰z = xz = a b³c³, which has 1 a but 3 b's and 3 c's — not in L_3eq.

Pick w=a^pb^pc^pd^p. |vxy|≤p is still shorter than any single block (length p), so vxy touches at most 2 of the 4 blocks, leaving at least 2 blocks' counts completely unpumped. Pumping breaks the required 4-way equality. (Verified exhaustively at p=3: all 169 valid splits fail.)

No — the CFL Pumping Lemma only ever disproves context-freeness (or, used positively, is consistent with it). Whether L_3eq is context-sensitive is a separate question, answered instead by exhibiting an actual context-sensitive grammar for it (Chapter 1, Section 1.3) — a different kind of evidence entirely.

v and y aren't free-floating choices — they're forced to be exactly the material between two occurrences of the same non-terminal along one root-to-leaf path (v to the left of the inner occurrence's subtree, y to the right, within the outer occurrence's span). Picking two unrelated chunks isn't a valid instance of the lemma's guarantee at all.

No — exactly as in the regular case (Chapter 3), the lemma is necessary, not sufficient. Some non-context-free languages can still admit strings and splits that happen not to produce a contradiction under this particular test; only an actual CFG (or PDA, Unit 4) proves context-freeness.

The regular machine processes a string as a single linear path through states, so a repeat gives exactly one loop, one pumped piece. The CNF machine processes a string as a tree, and a repeated non-terminal along one path splits the tree into three regions stacked vertically: above the first occurrence (u and z, outside), between the two occurrences (v on one side, y on the other, wrapping around the inner subtree), and the inner subtree itself (x). Because v and y are the two "wrapping" halves of the same loop-like structure, seen from a tree rather than a line, they must be pumped together — they're really one loop, just split by the branching structure into a left half and a right half.

S → S_bal | S_expr (renaming each grammar's own start symbol so they don't collide), with both original rule sets left completely untouched.

Round 1: A, B marked (both A→a, B→b are all-terminal). Round 2: S→AB has both A,B marked → S marked. Not empty — L(G)={ab}. (C never gets marked, and never needs to — it's unreachable from S, which the marking algorithm doesn't even need to notice, since it only asks whether S itself is generating.)

No such guarantee — and in fact this particular intersection is context-free: it's exactly {aⁿbⁿ : n≥0} (L_eq itself has no c's, forcing m=0 in L₁'s pattern too). The trap box's first warning applies directly: failing to be closed under an operation means no guarantee, not a guaranteed failure every time.

Infinite. Both A (A⇒aA) and B (B⇒bB) have productive cycles on their own, and both are reachable and generating (both can bottom out via their ε option) — so S=AB already generates aⁱb^j for every i,j≥0, infinitely many strings.

Being a larger class doesn't inherit smaller classes' closure properties — each closure property needs its own proof (or disproof) for each class. "Regular languages have property X" is evidence about regular languages specifically; CFLs sitting one tier up in Chapter 1's hierarchy says nothing by itself about which of X's proofs still go through.

No — it only ever inspects the grammar's rules directly (checking which non-terminals can eventually bottom out in terminals), never generates or tests any actual string. This is exactly why it terminates quickly regardless of whether L(G) would turn out to be small or unboundedly large.

Decidability asks "can an algorithm always correctly answer a yes/no question about a given grammar (or grammar plus string) in finite time" — a question about computability of grammar-level facts. Closure asks "if I combine languages from the class using some operation, must the result still belong to the same class" — a question about the class's structure under set operations. They're independent: a class can be closed under an operation while some decision problem about it remains hard or undecidable, or (as here) decidable in every individual case while still failing to be closed under a particular combination. CFLs happen to have nice decidability (membership, emptiness, finiteness) and only partial closure (three of five operations) — the two properties don't move together.

{E, F, S0, T} — every non-terminal whose CNF rules include a direct A→id option, exactly the same set as every other single-"id" span.

Combining table[0][1]={E,F,S0,T} with table[1][2]={A_plus} needs some rule A→X·A_plus with X in the first set — no CNF rule in this grammar ever ends with A_plus as its second symbol (A_plus only ever appears as the first symbol, in X₁→A_plusT). No match, cell stays empty.

table[0][3] (the full span). Following the same recurrence: table[0][1]={E,F,S0,T}, table[1][2]={A_star}, table[2][3]={E,F,S0,T}; table[1][3] combines the last two via X₂→A_starF → {X₂}; table[0][3] combines table[0][1] with table[1][3]={X₂} via rules ending in X₂: S₀→T·X₂, E→T·X₂, T→T·X₂ (all need T, present in table[0][1]) → {E, S₀, T}. S₀ present → accept.

Yes, it rejects correctly. Tokens are id,+,*,id. table[1][2]={A_plus}, table[2][3]={A_star} — combining two "bare operator" spans matches no rule (no rule has the shape A→A_plus·A_star), so table[1][3] stays empty, and every larger span depending on it stays empty too. The full span table[0][4] never contains S₀.

table[2][5] describes the substring from position 2 to 5, which is "id*id" — but that's a sub-span of the full string "id+id*id", not the whole input being parsed. Acceptance is only ever decided by table[0][n] (the full span, positions 0 to the very end); any other cell containing S₀ just means that particular substring, considered on its own, would be a valid expression — interesting, but not what's actually being asked.

Every cell's content is a complete, final answer about that exact span the moment it's computed — there's no "guess a rule, consume input, discover a dead end, undo" cycle, because CYK never consumes input in one direction while guessing; it only ever combines two answers that are already fully settled. There's nothing to walk back from.

The O(n³) bound relies on each cell needing only one split point to check per candidate rule, because every CNF rule has exactly two symbols on the right — a single number (the split position) fully describes how to divide a span in two. A rule with three or more symbols on the right would need multiple split points chosen simultaneously (dividing a span into three or more pieces), multiplying the number of combinations to check at each cell and pushing the time bound higher for every extra symbol a rule shape is allowed to have. CNF isn't just a convenience for stating the recurrence cleanly; it's specifically what pins the split-search cost at "one number to try," which is what keeps the whole algorithm cubic instead of worse.

A→BC and A→a only. A→aB mixes a terminal with a non-terminal — neither the "two non-terminals" nor the "one terminal alone" CNF shape.

Yes. GNF requires a terminal followed by zero or more non-terminals — zero is allowed, this is the base case, not an exception.

Each block alone already has length p, and |vxy|≤p — touching parts of all three blocks would require passing entirely through the middle block, needing more than p symbols. vxy is confined to at most two adjacent blocks.

Union: true (a simple wrapper rule). Intersection: false (L₁∩L₂=L_3eq, Section 5.3's counterexample).

If complement were closed, union-closure (true) plus complement-closure would force intersection-closure via L₁∩L₂=complement(complement(L₁)∪complement(L₂)) — but intersection-closure is false, so complement-closure must be false too.

Yes, empty. A is generating (A→a). B needs C generating; C needs S generating; S needs A and B generating — B and S and C form a closed loop with no terminal-only escape, so none of them ever get marked. S is never generating ⇒ L(G)=∅.

No — CFG equivalence is undecidable, unlike membership, emptiness, and finiteness, which all are.

table[0][n] — the span covering the entire input, checked for whether it contains the designated start symbol.

A non-terminal A has a productive cycle if A ⇒⁺ αAβ with α,β not both empty — A can derive a string containing itself, plus something extra. Repeating that derivation any number of times keeps adding more of α/β each time, generating unboundedly many distinct strings.

CYK's per-cell cost comes from trying every single split point of a span — a search that only stays a simple "one number" search because CNF rules have exactly two symbols on the right. GNF, for instance, doesn't have this binary-split property and isn't the normal form CYK is built around.