False statementConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

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.

FALSE: state elimination has a unique output expression

Statement

False claim: once a GNFA is fixed, state elimination always produces one unique final regular expression.

Facts & Assumptions

Given: The GNFA with start state $s$ , accept state $t$ , interior states $p, q$ , labels $λ (s, p) = a$ , $λ (p, t) = b$ , $λ (s, q) = a$ , $λ (q, t) = c$ , and every other label equal to $\emptyset$ .

[A1]

The statement refuted is: once a GNFA is fixed, state elimination always produces one unique final regular expression.

[L1]

By The GNFA state-elimination update, eliminating a state $r$ replaces each surviving label by $λ (p, q) + λ (p, r) (λ (r, r))^{*} λ (r, q)$ .

Refutation

technique · direct

1.1

Eliminate $p$ first. Applying [L1] without any algebraic simplification, and then eliminating $q$ , gives the final label $(\emptyset + a \emptyset^{*} b) + (a + a \emptyset^{*} \emptyset) (\emptyset + \emptyset \emptyset^{*} \emptyset)^{*} (c + \emptyset \emptyset^{*} b)$ .

L1given

1.2

Eliminating $q$ first and then $p$ instead gives $(\emptyset + a \emptyset^{*} c) + (a + a \emptyset^{*} \emptyset) (\emptyset + \emptyset \emptyset^{*} \emptyset)^{*} (b + \emptyset \emptyset^{*} c)$ .

L1given

2.1

These are different formal expression trees: already the first displayed outer summand ends in $b$ in step 1.1 and in $c$ in step 1.2. Thus [A1] is false even without imposing any simplification rules.

A1step 1.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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 and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)