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

Running the basic regular-language decision procedures on small DFA's

Example

Let $D_{e v e n}$ be the two-state DFA over ${0, 1}$ that accepts exactly the words with an even number of $1$ 's, and let $D_{e n d 1}$ be the two-state DFA that accepts exactly the words ending in $1$ .

Facts & Assumptions

Given: The DFA's $D_{e v e n}$ and $D_{e n d 1}$ just described.

[L1]

By DFA membership, emptiness, finiteness, equivalence, and containment are decidable, DFA membership, emptiness, finiteness, equivalence, and containment each have a decision procedure.

Verification

technique · direct

1.1given

Membership on the concrete input $1010$ returns "yes" for $D_{e v e n}$ , because the run sees two $1$ 's and finishes in the even-parity state.

1.2given

The emptiness test returns "nonempty" for both machines, and the finiteness test returns "infinite" for both: $D_{e v e n}$ accepts $ε, 00, 11, 0011, \dots$ , while $D_{e n d 1}$ accepts $1, 01, 001, \dots$ .

2.1step 1.1step 1.2

The equivalence test returns "not equivalent" because $ε \in L (D_{e v e n})$ but $ε \notin L (D_{e n d 1})$ . The containment tests also return "no" in both directions, because $1 \in L (D_{e n d 1}) ∖ L (D_{e v e n})$ and $00 \in L (D_{e v e n}) ∖ L (D_{e n d 1})$ .

3.1L1step 2.1∎

These outcomes match the decision procedures promised by [L1] on an explicit pair of DFA's.

Depends on

DFA membership, emptiness, finiteness, equivalence, and containment are decidable

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

John Watrous, Introduction to the Theory of Computing, Lecture 15: Encodings; examples of decidable languages (standard reference, not scraped)