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 context-free pumping lemma characterizes the context-free languages
Statement
False claim: a language is context-free exactly when it satisfies the ordinary Bar-Hillel pumping condition.
Facts & Assumptions
Given: Put , let be a new symbol, and set
The statement refuted is: a language is context-free exactly when it satisfies the ordinary Bar-Hillel pumping condition.
The proof of Context-free languages are not closed under intersection establishes that is not context free.
PDA's recognize exactly the context-free languages (PDAs recognize exactly the context-free languages), and context-free languages are closed under homomorphic image (Context-free languages are closed under union, concatenation, Kleene star, and homomorphism).
Refutation
We verify the ordinary pumping condition with pumping length . Let have length at least , with . If , pump the first letter of . If , then , and pump the unique initial . If and is nonempty, pump its first letter. In all three cases take the pumped letter as and take ; pumping preserves membership because it either keeps or changes the single initial to , which belongs to the second part of for every .
Suppose for contradiction that were context free. Let , which is regular. Choose a PDA for using [L3] and a DFA for . The product control consisting of the PDA state and DFA state, with the same stack operation as the PDA and with epsilon moves leaving the DFA state fixed, is a PDA for . Hence is context free.
It remains to treat with . For , take ; for , take . Put and let be the remaining suffix. Pumping produces respectively or , whose exponent is never . Thus , , and every pumped word lies in .
By definition, . Apply the homomorphism that deletes the initial symbol and fixes . Closure under homomorphism from [L3] would make context free, contradicting [L2]. Therefore is not context free.
Steps 1.1 and 2.1 show that satisfies the ordinary pumping condition, while step 2.2 shows that it is not context free. Thus [A1] is false.
Depends on
Used by
Dependency tree · two levels
8 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
- David S. Wise, A Strong Pumping Lemma for Context-Free Languages (standard reference, not scraped)
- Computer Science Stack Exchange, Example of a non-context-free language that nonetheless can be pumped (standard reference, not scraped)
- ROIFE BLOG, [形式语言] 06 Context-free Language (standard reference, not scraped)