How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Dropping epsilon closure changes the accepted language
Statement refuted
“For every epsilon-NFA, determinisation preserves the accepted language if the start closure is omitted, or if post-letter closure is omitted.” In the first variant only the start changes to ; in the second the start remains and the letter map changes to . Both variants retain the full power set and the final-subset intersection test.
Facts & Assumptions
Given: We test the two stated variants separately, writing .
An epsilon-NFA starts its extended transition at , closes every post-letter successor union, and accepts exactly when the resulting subset meets (Epsilon-NFAs, finite epsilon closure, and extended word transition).
The correct subset DFA has that closed start, those closed successor unions, and final subsets meeting , with exactly the same accepted language (Subset construction and its exact reachability invariant).
Counterexample
Let , , start , and , with . Put , , , and . All four domain entries are specified subsets of the finite state set, so this is an epsilon-NFA. Saturation from gives and then stays there; thus .
In the correct construction the empty word reaches , whose intersection with is , so it is accepted. In the first defective construction the empty word leaves the start at , whose intersection with is empty, so it is rejected. This mismatch occurs before any letter transition, even though all post-letter closures in that variant are retained.
In the second defective construction the start is correctly , but on the single letter its successor union is . Omitting closure leaves that set, disjoint from , so the variant rejects . The correct construction instead closes it to , which meets ; equivalently the original NFA has the accepting path .
Each defective rule still gives a total DFA on the finite power set: its letter outputs are subsets and each of its starts is a subset. The failures are therefore language failures, not missing transitions. The empty word distinguishes the first variant and distinguishes the second, refuting both universal preservation claims.
Source
The two-state witness is original. It tests the two separate closures in Aho, Lecture 3 §2; neither is dispensable in general.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
16 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Jean Gallier, Introduction to the Theory of Computation (2018), §§3.3–3.5 (standard reference, not scraped)
- Alfred Aho, COMS W3261 Lecture 3, §§1–2 (standard reference, not scraped)