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.1

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

givenF1construct
1.2

We claim that, for every word w, the run from ε ends at the state w when wP, and ends at when wP. 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.

constructinduction
2.1

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

step 1.2given
3.1

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

L1step 1.1step 2.1

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