The theory that builds a real compiler stage

δ_even(q₁,b)=q₁; δ_endsab(D₂,b)=D₀. New state: (q₁,D₀).

Swap F from {q₀} to {q₁}. The resulting language is exactly L_odd — the complement of "even a-count" is "odd a-count" (over the full alphabet {a,b}, with no other strings excluded).

Accept iff q-part is q₀ OR D-part is D₂: (q0,D0), (q0,D1), (q0,D2), (q1,D2) — four of the six states, matching fig 3.1's "∪" toggle.

Yes — set difference is intersection with a complement, L_even ∩ (L_ends-ab)̄, and both operations preserve regularity, so the combination does too. Accept rule: q-part is q₀ AND D-part is not D₂: (q0,D0), (q0,D1).

Try "ba": the NFA's active set ends at {p₀,p₁} wait — check directly: read b: {p0}; read a: {p0,p1}. Flipping accepting states to {p0,p1} (everything except the old p2) makes this flipped-NFA accept "ba" via p0 or p1 being active — correctly, since "ba" doesn't end in ab. Now try "ab" itself: active set ends at {p0,p2}; under the flipped rule only p0 or p1 count, and p0 IS active, so the flipped machine also accepts "ab" — incorrectly, since "ab" does end in ab and should be rejected by a true complement. The flip breaks precisely because "some thread is in a flipped-accepting state" isn't the same condition as "every thread failed the original acceptance" — confirming the trap box: complement needs a DFA.

The construction only ever produces a finite state set (bounded by |Q₁|×|Q₂|) with a fully total δ built from two already-total functions — which is, by definition, exactly another DFA. Since every DFA's language is regular, the result is automatically regular; there's no step in the recipe that could produce anything else.

L_even ∪ L_ends-ab = complement of ( (L_even)̄ ∩ (L_ends-ab)̄ ) — De Morgan's law translated directly into languages. Since complement and intersection are each already proven closed, chaining them (complement, then intersection, then complement again) never leaves the regular languages at any step — union closure is technically a free corollary of the other two, though this chapter still gave it its own direct product-construction proof since that's more useful for actually building the machine.

(1) |y| > 0 (never empty), (2) |xy| ≤ p (split happens early), (3) xyⁱz ∈ L for every i ≥ 0 (pump any number of times, including zero, and stay in the language).

x=aa, y=aa, z=b⁴ (check: |xy|=4≤p=4 ✓, |y|=2>0 ✓). At i=2: xy²z = aa·aaaa·bbbb = a⁶b⁴ — 6≠4, not in L_eq. Contradiction confirmed for this split (and, per the worked example, for every other valid split too).

Pick w=a^pb^pc^p. Any split with |xy|≤p lands entirely in the leading a's, so y=a^k, k≥1. Pumping to i=0 gives a^p−kb^pc^p, with a-count ≠ b-count — not in L_3eq. Every split fails identically. Not regular. (Numerically checked at p=3: all 6 splits fail.)

Pick w=a^p+1b^p (i=p+1>j=p, so w∈L_>). Any split with |xy|≤p lands in the leading a's (there are p+1 of them), so y=a^k, k≥1. Pumping to i=0: a^p+1−kb^p. Since k≥1, p+1−k≤p, so the a-count no longer exceeds the b-count — not in L_>. Not regular. (Verified at p=4: all 10 splits fail.)

The proof only checked one split (admittedly, per condition (2), it's the only shape a split can take here since the first p symbols are all a's — but the write-up needs to say that every valid split has y consisting only of a's, and argue that generally, rather than silently picking one convenient case and hoping the grader doesn't notice the gap).

No. The Pumping Lemma is a necessary condition of regularity (every regular language satisfies it), not a sufficient one. A non-regular language could still happen to have some strings admit a pumping length and a split that survives — passing this one check is weak evidence at best, never a proof. Proving regularity means exhibiting an actual DFA, NFA, regular grammar, or RE (Chapters 1–2), not surviving a pumping attempt.

Shared idea: a machine with finitely many states can't keep an unboundedly large count distinct forever — something must eventually repeat or collide. The difference between the two formal versions is where the argument starts: Myhill–Nerode works directly on the language (comparing strings aⁱ, a^j for future-behaviour differences, no machine needed at all), while the Pumping Lemma works by first assuming a machine/pumping-length exists and deriving a contradiction from how it would have to behave. Same destination, opposite starting assumptions.

No. The pattern requires the first symbol to be L (a letter); "9x" starts with a digit. "9x" would instead need to be scanned as NUMBER "9" followed by a separate IDENTIFIER "x" (two tokens).

IDENTIFIER "abc123" — one token. The pattern L(L+D)* happily consumes letters and digits in any mix after the first letter, and there's no character afterward to force a stop.

Both patterns match "true" at exactly the same length (4 characters) — a genuine tie, not resolved by "longest wins" since they're equally long. This needs an explicit priority rule (list BOOL's pattern before IDENTIFIER's, so BOOL wins ties) — the same style of fix as the keyword-table approach, just applied inside the DFA's tagging instead of after it.

NUMBER's pattern D+ matches "12" but has no transition on a letter, so it stops there: NUMBER "12", then restart at "if": IDENTIFIER "if" (later relabelled KEYWORD by the reserved-word table). Two tokens, in that order.

Not wrong exactly, but needlessly complicated — and it reintroduces the BOOL-style tie problem from 3.3.3 for every keyword, needing an explicit priority rule for each one. The table-lookup approach sidesteps this entirely: let IDENTIFIER's machine match "if" like any other identifier, and relabel afterward. Fewer machine states, one small table, same result.

Because the machine might walk past an accepting state into further non-accepting territory that still has live transitions (as "if" → "if1" does, briefly passing through non-obviously-different accepting states) before eventually dying. Only by remembering the last accepting position can the scanner correctly "back off" to the longest valid lexeme once it finally gets stuck, rather than being stuck with only whatever the current (possibly non-accepting, dead) state says.

Each regex, by Kleene's theorem, has a mechanically constructible equivalent NFA (RE→FA, Section 2.4). Unioning them under one shared start — itself just the union construction from that same theorem — produces a single NFA for "any of these patterns." Subset construction (Section 2.3) turns it into a DFA, minimization (Section 2.2) shrinks it, and tagging each accepting state with its originating token name finishes the job. Every step is an algorithm already covered, chained together; nothing requires a human to think up new automaton structure by hand, which is exactly why tools like flex can generate a scanner in milliseconds from a spec file.

S→^xI (accept). No transition on '<' from I — emit IDENTIFIER "x", pos→1. S→^<LT (accept). No transition on 'y' from LT — emit LT "<", pos→2. S→^yI (accept), end of input — emit IDENTIFIER "y". Stream: IDENTIFIER "x", LT "<", IDENTIFIER "y".

S→¹N→²N (accept both steps). No transition on 'a' from N — emit NUMBER "12", pos→2. S→^aI→^bI, end of input — emit IDENTIFIER "ab". Stream: NUMBER "12", IDENTIFIER "ab".

NUMBER "12" emits normally (pos→2). Starting fresh at '#': S has no transition on '#' at all (not L, D, <, or =), so lastAcceptPos is never set even once — LEXICAL ERROR at position 2, the '#'. (Verified by direct simulation.)

Only S needs a new transition: currently δ(S,'=')=DEAD; change it to a new accepting state ASSIGN with no further outgoing transitions of its own (mirroring how LT was built before LE existed). Nothing about I, N, LT, or LE changes — adding a token only ever adds machinery reachable from S, consistent with how the union construction (Section 2.4) works.

They stopped extending at the first accepting state instead of continuing while transitions remained live — the first-match mistake Section 3.3 warned about, not the correct longest-match/maximal-munch behaviour the algorithm actually specifies.

Each token is scanned independently — the machine has no memory of "IDENTIFIER" vs "NUMBER" context once a token boundary is cut; every new attempt starts from the same blank slate S, exactly as if scanning a brand-new, shorter input starting at that position. This is what makes the combined DFA reusable token after token without rebuilding anything.

No — this is the union-via-NFA-gluing-then-subset-construction route (Section 2.4's Kleene construction), not the product construction. Product construction (Section 3.1) tracks all component machines' states simultaneously as a tuple, growing multiplicatively (|Q₁|×|Q₂|×…); this scanner instead merges the token patterns into one shared exploration from a single start, growing more like a sum than a product, precisely because at most one "kind" of token is ever being attempted at a time from S. Both routes are valid closure-preserving constructions for union; they just answer different design needs.

12 (3×4) — possibly fewer reachable in practice, but the construction itself always builds the full |Q₁|×|Q₂| set before any pruning.

False. Complement requires a total DFA; an NFA's "some thread accepts" condition doesn't invert cleanly into "some thread accepts" for the complement (Section 3.1's worked trap on "ab").

It forces the split to happen within the first p symbols of w — which is exactly what pins y down to a predictable shape (e.g., "all a's" for w=a^pb^p) and makes the contradiction constructible. Without it, y could be chosen anywhere, including a mix that might survive pumping harmlessly.

No. The lemma is necessary, not sufficient. Surviving pumping on some strings is consistent with regularity but doesn't establish it — only an explicit DFA/NFA/RE/regular grammar does that.

"counter" = lexeme (the actual text). IDENTIFIER = token (the category). L(L+D)* = pattern (the rule deciding membership).

IDENTIFIER "a1", one token — 'a' starts it as an identifier, and the digit that follows is allowed to continue it (L(L+D)* permits digits after the first letter).

LEXICAL ERROR is reported at the token's start position — there is no valid token boundary to back off to, which is different from the routine "got stuck after a valid accept" case.

Neither is guaranteed. The union-closure theorem requires both inputs regular to promise anything; with one input non-regular, the union could go either way (e.g. L₁=Σ* makes the union Σ*, regular, regardless of what L₂ is) — no general conclusion follows from the theorem alone.

5 symbols — reading 5 symbols means 6 state-visits total (including the start), which by pigeonhole must repeat some state among only 5 available. This is exactly the pumping length threshold |w|≥p with p=5.

S has no transition defined for '#' — the inner loop of the algorithm never executes even once, lastAcceptPos stays unset, and a LEXICAL ERROR is reported immediately at position 0, before any other token is attempted.