Alphabeta Math
ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

Adding a sink turns the published prefix automaton for avoiding 11 into a DFA

Example

Let B={11} over the alphabet {0,1}. The published proper-prefix state set is SB={ε,1}. Adjoin a sink state ⊥, keep ε and 1 accepting, and define the transitions by

δ(ε,0)=ε,δ(ε,1)=1, δ(1,0)=ε,δ(1,1)=⊥,δ(⊥,0)=⊥,δ(⊥,1)=⊥.

This DFA accepts exactly the binary words with no factor 11.

Facts & Assumptions

Given: The forbidden-factor set B={11} over {0,1}.

[L1]

The published prefix automaton extends canonically to a DFA for the factor-avoidance language by adjoining a sink and declaring the states in SB accepting, by The published prefix automata extend canonically to DFAs for factor-avoidance languages.

Verification

technique · direct
1.1

The only proper prefixes of the forbidden word 11 are ε and 1, so these are exactly the nonsink states. The missing transition is from 1 on input 1, and it must go to the sink because the extended word 11 already contains the forbidden factor.

given
1.2

Once the machine reaches ⊥, the forbidden factor has already appeared, so looping at ⊥ on both letters is the correct total completion. The words ε, 1, 10, and 1010 stay in the accepting states, while 11 and 1011 reach ⊥.

given
2.1

This is exactly the sink-state completion described by [L1], so the resulting DFA recognizes the binary words avoiding 11.

L1step 1.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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