Alphabeta Math
CounterexampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-09
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 {q0}; in the second the start remains E({q0}) and the letter map changes to ν(S,a)=qSδ(q,a). Both variants retain the full power set and the final-subset intersection test.

Facts & Assumptions

Given: We test the two stated variants separately, writing E=ECl.

[F1]

An epsilon-NFA starts its extended transition at E({q0}), closes every post-letter successor union, and accepts exactly when the resulting subset meets F (Epsilon-NFAs, finite epsilon closure, and extended word transition).

[F2]

The correct subset DFA has that closed start, those closed successor unions, and final subsets meeting F, with exactly the same accepted language (Subset construction and its exact reachability invariant).

Counterexample

1.1

Let Q={p,q}, Σ={a}, start p, and F={q}, with pq. Put δ(p,ε)={q}, δ(q,a)={p}, δ(p,a)=, and δ(q,ε)=. All four domain entries are specified subsets of the finite state set, so this is an epsilon-NFA. Saturation from {p} gives {p,q} and then stays there; thus E({p})={p,q}.

constructF1
2.1

In the correct construction the empty word reaches {p,q}, whose intersection with F is {q}, so it is accepted. In the first defective construction the empty word leaves the start at {p}, whose intersection with F is empty, so it is rejected. This mismatch occurs before any letter transition, even though all post-letter closures in that variant are retained.

step 1.1F1F2given
2.2

In the second defective construction the start is correctly {p,q}, but on the single letter a its successor union is δ(p,a)δ(q,a)={p}={p}. Omitting closure leaves that set, disjoint from F, so the variant rejects a. The correct construction instead closes it to E({p})={p,q}, which meets F; equivalently the original NFA has the accepting path pεqapεq.

step 1.1F1F2given
3.1

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 a distinguishes the second, refuting both universal preservation claims.

step 2.1step 2.2F2discharge-construct

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