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.

✓ 3 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 3 also cleared it.

Deterministic Finite Automata and Regular Languages: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples compute one extended transition explicitly, show how adjoining a sink repairs the published 11-avoidance prefix automaton into a total DFA, and exhibit the minimal missing-edge picture that fails to define a DFA at all.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

Computing $δ^{} (q, u v)$ as $δ^{} (δ^{*} (q, u), v)$

Example

Consider the DFA over ${a, b}$ with states $q_{0}, q_{1}, q_{2}, q_{3}$ , where:

$q_{0}$ means "no nonempty suffix of the input is a prefix of abb",
$q_{1}$ means "the current suffix is a",
$q_{2}$ means "the current suffix is ab",
$q_{3}$ means "the current suffix is abb".

Take $q_{0}$ as the start state and $F = {q_{3}}$ as the accepting set.

Its transitions are

δ (q_{0}, a) = q_{1}, δ (q_{0}, b) = q_{0}, δ (q_{1}, a) = q_{1}, δ (q_{1}, b) = q_{2},

δ (q_{2}, a) = q_{1}, δ (q_{2}, b) = q_{3}, δ (q_{3}, a) = q_{1}, δ (q_{3}, b) = q_{0} .

Take $u = a b$ and $v = a b b$ .

Then $δ^{*} (q_{0}, u v) = δ^{*} (q_{0}, a b a b b) = q_{3} = δ^{*} (δ^{*} (q_{0}, a b), a b b) .$

Facts & Assumptions

Given: The DFA above with start state $q_{0}$ , accepting set $F = {q_{3}}$ , and the words $u = a b$ and $v = a b b$ .

[L1]

Extended transition respects concatenation: $δ^{*} (p, u v) = δ^{*} (δ^{*} (p, u), v)$ , by Extended DFA transition respects concatenation.

[L2]

Acceptance is determined by the final state reached after reading the whole word, by Acceptance of a word by a DFA and the recognized language.

Verification

technique · direct

1.1

Compute directly that $δ^{*} (q_{0}, a b) = q_{2}$ , because $q_{0} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2}$ .

given

1.2

Reading the whole concatenated word at once gives $q_{0} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{b}{\to} q_{3}$ , so $δ^{*} (q_{0}, u v) = q_{3}$ as well.

given

2.1

Continuing from $q_{2}$ , we get $q_{2} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{b}{\to} q_{3}$ , so $δ^{*} (q_{2}, a b b) = q_{3}$ . Therefore $δ^{*} (δ^{*} (q_{0}, u), v) = q_{3}$ .

givenstep 1.1

3.1

The two calculations agree, exactly as [L1] predicts. In particular the word $a b a b b$ lands in the accepting state $q_{3}$ , consistent with [L2].

L1L2step 2.1step 1.2∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

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 $S_{B} = {ε, 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 $S_{B}$ 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∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

A missing `1`-transition shows the drawn machine is not yet a DFA

Statement refuted

The statement "a DFA transition diagram may omit a sink without changing totality" is false.

Facts & Assumptions

Given: The alphabet $Σ = {0, 1}$ and the one-state picture with only the loop $q \overset{0}{\to} q$ .

[A1]

The statement refuted is: omitting a sink transition does not affect whether the diagram defines a DFA.

[L1]

A DFA requires a total transition function on $Q \times Σ$ , by Deterministic finite automata.

Counterexample

technique · direct

1.1

The picture specifies a transition on input 0 but no transition on input 1. So the pair $(q, 1)$ has no image.

given

2.1

By [L1], that means the picture does not define a DFA at all. Adding a sink state with a 1-edge repairs the omission, which is exactly why the original claim fails.

L1step 1.1

3.1

Therefore this one-state picture is a counterexample to [A1].

A1step 2.1∎

Deterministic Finite Automata and Regular Languages: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Computing δ∗(q,uv)δ∗(q,uv) as δ∗(δ∗(q,u),v)δ∗(δ∗(q,u),v)

Example

Facts & Assumptions

Verification

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

Example

Facts & Assumptions

Verification

A missing 1-transition shows the drawn machine is not yet a DFA

Statement refuted

Facts & Assumptions

Counterexample

Sources

Computing $δ^{} (q, u v)$ as $δ^{} (δ^{*} (q, u), v)$

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

A missing `1`-transition shows the drawn machine is not yet a DFA