Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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.

Every DFA language is denoted by a regular expression

Statement

If D is a DFA over Σ, then there exists a regular expression R over Σ such that L(R)=L(D).

Facts & Assumptions

Given: A DFA D=(Q,Σ,δ,q0,F).

[L1]

By Generalized NFA's and their accepted languages, a GNFA accepts the words read along paths from its start state to its accept state, and the intermediate-state restriction is tracked by the sets PK(p,q).

[L2]

By The GNFA state-elimination update, eliminating an interior GNFA state uses the update λ(p,q)=λ(p,q)+λ(p,r)(λ(r,r))λ(r,q).

[L3]

By State elimination preserves the language between every surviving state pair, one elimination step preserves the path language between every surviving state pair.

[L4]

By Acceptance of a word by a DFA and the recognized language, a word belongs to L(D) exactly when the run of D from q0 ends in a state of F.

Proof

technique · direct
1.1

Form a GNFA G0 by adjoining a new start state s and a new accept state t to the DFA states. Put the label ε on sq0 and on each edge ft with fF. For DFA states p,qQ, label pq by the union of all letters aΣ with δ(p,a)=q, and use on every remaining ordered pair. By [L4], a word is accepted by D exactly when it labels a path from s to t through the old DFA states, so L(D)=PQG0(s,t).

L1L4givenconstruct
2.1

Eliminate the states of Q one at a time. At each step use the update from [L2]. By [L3], after each elimination the start-to-accept path language is unchanged. Therefore, when all interior states have been removed, the resulting two-state GNFA Gf still satisfies L(Gf)=L(D).

L2L3step 1.1
3.1

In Gf the only possible accepting paths go directly from s to t, so by [L1] the accepted language is exactly the denotation of the sole label on that edge. Hence some regular expression denotes L(D).

L1step 2.1

Depends on

Used by

Dependency tree · two levels

12 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