False statementConstruction: AI-adaptedVerification: 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: the pumping lemma still works if its quantifiers are reordered

Statement

In the pumping lemma, once a pumping length is fixed, every legal decomposition of every sufficiently long word pumps.

Facts & Assumptions

Given: The regular language $O : = {x \in {0, 1}^{*} : ∣ x ∣ is odd} .$

[L1]

By The pumping lemma for regular languages, a regular language only guarantees the existence of a good decomposition for each sufficiently long word.

Refutation

technique · direct

1.1

The language $O$ is regular: a two-state DFA that toggles parity after each input symbol accepts exactly the words of odd length.

givenconstruct

1.2

Fix any pumping length $p \geq 1$ and take $w : = 0^{2 p + 1} \in O$ . The decomposition $x : = ε$ , $y : = 0$ , $z : = 0^{2 p}$ is legal because $∣ x y ∣ = 1 \leq p$ and $∣ y ∣ > 0$ , but pumping once gives $x z = 0^{2 p}$ , whose length is even, so $x z \notin O$ . Thus this legal decomposition does not pump.

givenconstruct

2.1

Step 1.2 shows that a regular language can have bad legal decompositions even though [L1] supplies some good one. Therefore the quantifiers cannot be reordered as stated, and the statement is false.

L1step 1.1step 1.2∎

Depends on

The pumping lemma for regular languages

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)
Eric Blais, Models of Computation, 20. Nonregular Languages (standard reference, not scraped)