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

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.

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

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

1.2given

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.

2.1givenstep 1.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}$ .

3.1L1L2step 2.1step 1.2∎

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

Depends on

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

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

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