Alphabeta Math
PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-30
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 finite language is regular

Statement

Every finite language over an alphabet Σ is regular.

Facts & Assumptions

Given: A finite language L⊆Σ∗.

[L1]

A language over Σ is regular exactly when it is recognized by some DFA over Σ, by Regular languages.

[F1]

Let P be the set consisting of ε together with every prefix of every word in L. Because L is finite and each word has only finitely many prefixes, the set P is finite.

Proof

technique · direct
1.1givenF1construct

Define a machine D with state set P∪{⊥}, start state ε, accepting set F=L, and transition rule δ(p,a)={pa,if pa∈P,⊥,if pa∉P,δ(⊥,a)=⊥. By [F1] the state set is finite, and the transition rule is total on (P∪{⊥})×Σ.

1.2constructinduction

We claim that, for every word w, the run from ε ends at the state w when w∈P, and ends at ⊥ when w∉P. This follows by induction on the length of w: appending a letter keeps the machine at the longer prefix exactly when that longer word still lies in P, and otherwise sends the run to ⊥, where it remains.

2.1step 1.2given

A word w is accepted by D exactly when the final state lies in F=L. By step 1.2 this happens exactly when w∈L, because every word in L is one of its own prefixes and therefore belongs to P.

3.1L1step 1.1step 2.1∎

Thus L=L(D) for the DFA from step 1.1, so [L1] shows that L is regular.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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