Alphabeta Math
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 characterizes the regular languages

Statement

If a language satisfies the regular pumping property, then it is regular.

Facts & Assumptions

Given: The language G:={wwRv:w,v{0,1}+, wε}.

[L2]

By Infinitely many pairwise distinguishable prefixes force nonregularity, a language with infinitely many pairwise distinguishable prefixes is not regular.

Refutation

technique · direct
1.1

The language G satisfies the pumping conclusion with pumping length 4. If s=wwRvG with w2, write w=au with uε and choose x=ε, y=a, z=uuRav; then xz=uuRavG, the original word is xyzG, and for every i2 the word xyiz=aiuuRav lies in G by using the one-letter witness word a and the nonempty suffix ai2uuRav.

givenconstruct
1.2

For each n1, let pn:=(01)n and xn:=(10)n1. Then pnxn=(01)n(10)n1 lies in G by taking witness word (01)n and suffix 1. If m>n and pmxn were in G, write pmxn=rrRv with rε and v{0,1}+. The word pmxn=(01)m(10)n1 has exactly one doubled adjacent pair, namely the middle 11 at the junction between (01)m and (10)n1. Any prefix of the form rrR has a doubled middle pair at the boundary between r and rR, so that boundary must be this unique 11. Hence r=2m, which makes the palindromic prefix rrR have length 4m. But pmxn=2m+2n+1<4m+1 because n<m, so no such factorization with nonempty v exists. Therefore pmxnG, and the prefixes pn are pairwise distinguishable.

L2given
2.1

If instead w=1, then s=aav with v2 because s4; writing v=bt and choosing x=aa, y=b, z=t pumps entirely inside the nonempty suffix v, so every xyiz stays in G. Thus every sufficiently long word in G has a legal pumping decomposition.

step 1.1given
3.1

Step 1.2 and [L2] show that G is not regular, while steps 1.1 and 2.1 show that G still has the regular pumping property. Therefore the pumping property does not characterize regularity, and the statement is false.

L2step 1.1step 2.1step 1.2

Depends on

Used by

Dependency tree · two levels

9 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