CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 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.

A non-context-free language can still satisfy the Bar-Hillel pumping condition

Statement refuted

The false statement claims that the ordinary CFL pumping condition characterizes the context-free languages. Put $K : = {a^{n} b^{n} c^{n} : n \geq 0}, L : = s K \cup {s^{r} q : r \neq 1, q \in {a, b, c}^{*}},$ where $s$ is a new symbol. The language $L$ is a counterexample.

Facts & Assumptions

Given: The language $L$ displayed above.

[L1]

By FALSE: the context-free pumping lemma characterizes the context-free languages, the refuted claim is that satisfying the ordinary pumping condition is equivalent to being context-free.

[L2]

The proof of Context-free languages are not closed under intersection establishes that $K$ is not context free.

[L3]

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

Counterexample

technique · direct

1.1

Take pumping length $p : = 3$ and write a word of $L$ as $s^{r} q$ . If $r = 0$ , pump the first letter of $q$ ; if $r = 1$ , pump the initial $s$ ; if $r \geq 2$ and $q$ is nonempty, pump its first letter. Taking $w = x = ε$ gives $∣ v w x ∣ \leq 3$ , and every pump remains in $L$ .

givencases

1.2

Suppose $L$ were context free and let $R : = {s a^{i} b^{j} c^{k} : i, j, k \geq 0}$ . A product of a PDA for $L$ from [L3] with a DFA for the regular language $R$ is a PDA for $L \cap R = s K$ . The homomorphism deleting $s$ would then make $K$ context free by [L3], contradicting [L2].

L2L3assume-contraconstructdischarge-contradiction

2.1

If the word is $s^{r}$ with $r \geq 3$ , pump $s^{3}$ when $r = 3$ and pump $s^{2}$ when $r \geq 4$ . Pumping never leaves exactly one initial $s$ , so every pumped word again lies in $L$ . Thus $L$ satisfies the ordinary CFL pumping condition.

step 1.1cases

3.1

Hence $L$ satisfies ordinary pumping but is not context free, so it refutes the claim in [L1].

L1step 2.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

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

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)