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.

Regular Expressions and Kleene's Theorem: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples build an automaton for a concrete regular expression, run the standard DFA decision procedures on tiny machines, and separate formal syntax from the language that syntax denotes.

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 →

Constructing an epsilon-NFA for $(a + b)^{*} a b b$

Example

After the standard Thompson construction and the obvious epsilon-edge simplifications, one convenient epsilon-NFA for $(a + b)^{*} a b b$ has states $q_{0}, q_{1}, q_{2}, q_{3}$ , start state $q_{0}$ , accepting state $q_{3}$ , and transitions

$q_{0} \overset{a}{\to} q_{0}, q_{0} \overset{b}{\to} q_{0}, q_{0} \overset{a}{\to} q_{1}, q_{1} \overset{b}{\to} q_{2}, q_{2} \overset{b}{\to} q_{3} .$

It is an epsilon-NFA because ordinary NFA's are the special case with no $ε$ -moves.

Facts & Assumptions

Given: The displayed machine with start state $q_{0}$ and accepting state $q_{3}$ .

[L1]

By Every regular expression has an equivalent epsilon-NFA, a regular expression has an equivalent epsilon-NFA.

Verification

technique · direct

1.1given

Any word of the form $x a b b$ with $x \in {a, b}^{*}$ is accepted: stay in $q_{0}$ while reading the prefix $x$ , then use the branch $q_{0} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{b}{\to} q_{3}$ on the final three letters.

2.1step 1.1

Conversely, every accepting run must finish with the forced chain $q_{0} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{b}{\to} q_{3}$ , because $q_{3}$ is reached only from $q_{2}$ by a $b$ -edge and $q_{2}$ is reached only from $q_{1}$ by a $b$ -edge. Therefore any accepted word ends in $a b b$ , and the earlier letters are exactly the ones read by the two loops at $q_{0}$ .

3.1L1step 1.1step 2.1∎

Hence this machine recognizes the words ending in $a b b$ , which is the language of $(a + b)^{*} a b b$ . This is the concrete instance promised by [L1].

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

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.

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

The expression $a + b$ is not literally the set ${a, b}$

Statement refuted

The false statement claims that a regular expression is literally the same object as the language it denotes.

Facts & Assumptions

Given: The regular expression $a + b$ .

[L1]

By FALSE: a regular expression is the same object as its denoted language, the refuted claim is that a regular expression is literally the same object as its denoted language.

Counterexample

technique · direct

1.1given

The object $a + b$ is a formal expression, while its denotation is the language ${a, b}$ .

2.1L1step 1.1∎

A formal expression and a two-element set of words are not literally the same object, so the example contradicts the claim in [L1].

Regular Expressions and Kleene's Theorem: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Constructing an epsilon-NFA for (a+b)∗abb(a+b)∗abb

Example

Facts & Assumptions

Verification

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

Example

Facts & Assumptions

Verification

The expression a+ba+b is not literally the set {a,b}{a,b}

Statement refuted

Facts & Assumptions

Counterexample

Sources

Constructing an epsilon-NFA for $(a + b)^{*} a b b$

The expression $a + b$ is not literally the set ${a, b}$