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 · 1 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. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Nondeterministic Finite Automata and Subset Construction: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples realize the DFA-to-NFA embedding, display a small subset construction that really adds states, and refute the mistaken universal-branch reading of NFA acceptance.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-12Open item page →

Viewing a small DFA as an NFA with singleton transitions

Example

Consider the two-state DFA over ${0, 1}$ with states $e, o$ , start state $e$ , accepting state $e$ , and transitions that toggle between $e$ and $o$ on input $1$ and stay fixed on input $0$ .

Regarded as an NFA, the same machine has singleton one-letter transition sets and no epsilon-transitions. It still recognizes the language of words with an even number of $1$ 's.

Facts & Assumptions

Given: The parity DFA just described.

[L1]

By Every DFA is an NFA, every DFA can be viewed as an NFA by replacing each one-letter transition by a singleton transition set and adding no $ε$ -moves.

Verification

technique · direct

1.1given

The parity DFA has exactly one next state on each input symbol, so the associated NFA has transition sets ${e}$ or ${o}$ and never branches.

2.1L1step 1.1

Because there is only one live branch on every input, the NFA reaches exactly the same state as the DFA after every word. Therefore it accepts exactly the words with an even number of $1$ 's.

3.1L1step 2.1∎

This is a concrete instance of the DFA-to-NFA embedding from [L1].

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-12Open item page →

A three-state NFA whose equivalent DFA needs four states

Example

Let $L \subseteq {0, 1}^{*}$ be the language of words whose second symbol from the end is $1$ .

An NFA for $L$ has three states: a start state that loops on both symbols, a state entered when the machine guesses that two symbols remain and the current symbol is $1$ , and an accepting state reached after one more symbol. The subset construction on this NFA produces four reachable subsets.

Facts & Assumptions

Given: The language of words over ${0, 1}$ whose second symbol from the end is $1$ .

[L1]

By The subset-construction DFA, the subset construction turns each reachable set of NFA states into a DFA state.

[L2]

By The subset construction can require exponentially many states, nondeterministic branching can force a deterministic simulation to keep track of several possibilities at once.

Verification

technique · direct

1.1given

The three NFA states represent "still guessing", "just guessed the penultimate 1", and "accepted after one more symbol". On a word such as $010$ , the machine may stay in the guessing state for the first symbol and then branch correctly at the second symbol, where the symbol $1$ really is penultimate.

2.1L1step 1.1

The reachable subsets are the four nonempty sets ${q_{0}}$ , ${q_{0}, q_{1}}$ , ${q_{0}, q_{2}}$ , and ${q_{0}, q_{1}, q_{2}}$ . They have different future acceptance behavior: the two sets containing $q_{2}$ accept $ε$ while the other two do not; ${q_{0}, q_{1}}$ accepts the one-letter suffix $0$ while ${q_{0}}$ does not; and ${q_{0}, q_{1}, q_{2}}$ accepts $0$ while ${q_{0}, q_{2}}$ does not. Therefore [L1] makes them four distinct DFA states.

3.1L2step 2.1∎

This concrete four-state DFA illustrates the general phenomenon from [L2]: subset states encode simultaneous NFA possibilities.

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

One accepting branch is enough for an NFA to accept

Statement refuted

The statement "an NFA accepts a word only if every branch accepts" is false.

Facts & Assumptions

Given: The NFA and input word $a b b$ from FALSE: an NFA accepts only if every branch accepts.

[A1]

The statement refuted is: an NFA accepts a word only if every branch accepts.

[L1]

The false statement's refutation already exhibits one accepting branch and one rejecting branch on the same input, by FALSE: an NFA accepts only if every branch accepts.

Counterexample

technique · direct

1.1L1given

On the input $a b b$ , one branch follows the path $q_{0} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{b}{\to} q_{3}$ and accepts, while another branch stays on the start-state loop too long and rejects.

2.1step 1.1

Therefore the same machine and the same word witness that acceptance can occur even when not every branch accepts.

3.1A1step 2.1∎

This contradicts [A1], so the displayed NFA on $a b b$ is a counterexample.

Nondeterministic Finite Automata and Subset Construction: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Viewing a small DFA as an NFA with singleton transitions

Example

Facts & Assumptions

Verification

A three-state NFA whose equivalent DFA needs four states

Example

Facts & Assumptions

Verification

One accepting branch is enough for an NFA to accept

Statement refuted

Facts & Assumptions

Counterexample

Sources