ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-12

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.

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

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.

given

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

L1step 1.1

3.1

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

L2step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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

Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)