False statementConstruction: Literature-sourcedVerification: 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.

FALSE: an NFA accepts only if every branch accepts

Statement

False claim: an NFA accepts a word only when every computation branch on that word accepts.

Facts & Assumptions

Given: The NFA over $Σ = {a, b}$ with states $q_{0}, q_{1}, q_{2}, q_{3}$ , start state $q_{0}$ , accepting state $q_{3}$ , loops $q_{0} \overset{a}{\to} q_{0}$ and $q_{0} \overset{b}{\to} q_{0}$ , and extra transitions $q_{0} \overset{a}{\to} q_{1} \overset{b}{\to} q_{2} \overset{b}{\to} q_{3}$ .

[A1]

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

[L1]

By Acceptance of a word by an NFA and the recognized language, an NFA accepts a word exactly when the set of states reachable after reading the word contains an accepting state.

Refutation

technique · direct

1.1

On input $a b b$ , one computation branch takes the transition $q_{0} \overset{a}{\to} q_{1}$ at the first letter and then follows the two $b$ -transitions to $q_{3}$ , so this branch accepts. Another branch stays on the loop at the first letter, reaches $q_{0}$ again after reading the first $b$ , and then has no way to complete the suffix $b b$ to $q_{3}$ , so that branch rejects.

given

2.1

Step 1.1 shows that after reading $a b b$ an accepting state is reachable, even though not every branch accepts. Therefore [L1] says the machine accepts $a b b$ .

L1step 1.1

3.1

This contradicts [A1]. NFA acceptance is existential over branches, not universal.

A1step 2.1∎

Depends on

Acceptance of a word by an NFA and the recognized language

Used by

One accepting branch is enough for an NFA to accept Counterexample

Dependency tree · two levels

3 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)