Question bank — Pumping lemma for CFLs

True — the lemma is a necessary property of all CFLs, so passing it is expected and proves nothing on its own.

False — the lemma is necessary but not sufficient; some non-CFLs still satisfy a pumping-style property, so you cannot conclude "CFL" from it. To prove CFL you must exhibit a grammar or PDA.

False — it has two pieces $v$ and $y$ pumped together with the same exponent $i$, because a repeated variable $A{\Rightarrow }^{\ast }vAy$ grows the parse tree on both sides.

False — they always share the same $i$: $u{v}^{i}x{y}^{i}z$. They come from one repeated variable, so one loop-count controls both.

False — it means they are not both empty; one of them may be empty as long as the other has at least one symbol.

True — the adversary hands us $p$, then we pick a clever $w\in L$ with $|w|\ge p$. This is the step where good choices win.

False — the adversary chooses any valid split (respecting $|vy|\ge 1$ and $|vxy|\le p$); our job is to beat every such split.

False — it can only ever prove a language is not context-free (by contradiction). It is a one-directional tool.

False — the lemma says every long string pumps, so one good-behaving string proves nothing. To refute you need one bad witness that no split can pump.

True — that single un-pumpable witness contradicts the lemma, so $L$ cannot be a CFL.

False — $p$ is a constant of the language (roughly $2^b$ where $b$ is the number of variables in a CNF grammar). It is fixed before any $w$ is chosen.

True — CNF makes parse trees binary so we can bound leaves by height, but the lemma's statement holds for the language regardless of which grammar you started from.

Error: $a^p\notin L$ unless $p$ also equals the $b$- and $c$-counts, and even so it is a weak witness. The correct witness is $a^p{b}^p{c}^p$, whose three blocks the window $|vxy|\le p$ cannot all span.

Error: a weak witness pumping proves nothing (necessary-not-sufficient). Use a harder witness like $0^p{1}^p{0}^p{1}^p$, and note the game only ever proves not-CFL, never CFL.

Error: the adversary picks any valid split; you cannot assume where $v,y$ land. You must argue the contradiction holds for all placements consistent with $|vxy|\le p$.

Error: a window of length $\le p$ straddling a boundary can touch two adjacent letter types; it just cannot span from an $a$ to a $c$ (they are $\ge p$ apart). The argument must allow two types.

Error: surviving one $i$ is not enough for you, but also does not help the language. You need some $i$ (0 or 2) that ejects the string, and you only prove not-CFL, never CFL.

Slight but real error: it bounds the whole window $v,x,y$ together by $p$, which does bound $v$ and $y$ individually — but the useful fact is the combined window is localized, not that any single piece is large.

Error: pumping up only works when $vy$ omits $c$ (raising an earlier count above $k$). If $vy$ omits $a$, you must pump down ($i=0$) to shrink $j$ or $k$ below the fixed $a$-count. Both cases are required.

A DFA loop repeats a linear cycle giving one piece; a CFG's repeated variable $A{\Rightarrow }^{\ast }vAy$ sits inside a branching parse tree, inserting symbols on both the left ($v$) and right ($y$).

A binary tree of height $\le b$ has at most $2^b$ leaves; needing strictly more than $2^b$ leaves forces height $>b$, which by pigeonhole forces a repeated variable on some path. The strict inequality is exactly why we exceed $2^b$.

Picking the lowest pair keeps the upper $A$'s subtree small (bounded height), which is what guarantees $|vxy|\le p$. A higher pair could give an arbitrarily large window.

In CNF a node $A\to BC$ has two children, so the upper $A$'s subtree is strictly larger than the lower $A$'s subtree; the extra symbols are exactly $v$ and $y$, so at least one is non-empty. CNF's ban on unit/$\epsilon$-rules prevents $A\Rightarrow A$.

The bounded window $|vxy|\le p$ can only reach a couple of adjacent blocks, so pumping unavoidably breaks the balance a third block requires — the interaction is what makes the string un-pumpable.

Because the quantifiers alternate: $\exists p$ (adversary), $\forall w$ becomes we choose one bad $w$, $\forall$ splits (adversary), $\exists i$ (we choose). Modelling it as a game keeps the "who chooses what" straight.

Pumpability is only necessary; certain non-CFLs mimic it, so the property is too weak to certify membership. Positive proof needs an explicit grammar or PDA.

CNF forces every internal parse-tree node to have exactly two children, making the tree binary so that "many leaves ⇒ tall tree ⇒ repeated variable" is a clean counting argument.

No — the guarantee applies only to $w$ with $|w|\ge p$. Short strings are exempt, which is why witnesses must be long enough.

Yes — $x$ may be empty; only $|vy|\ge 1$ is required. The repeated variable might derive an empty core while $v,y$ carry the growth.

Not directly — $\epsilon$ is shorter than $p$, so the length hypothesis $|w|\ge p$ excludes it; the lemma makes no claim about it.

You delete the loop, removing the symbols in $v$ and $y$. This is the tool of choice when $vy$ sits in blocks whose counts you want to shrink below a fixed reference block.

Every finite language is context-free (and regular), so it trivially satisfies the lemma — you just take $p$ larger than the longest string, making the "$|w|\ge p$" clause vacuous. No contradiction is derivable, as expected.

Yes — it is context-free, so it pumps (split so $v$ sits in the $a$'s and $y$ in the $b$'s, adding equal counts). This is a reminder that pumping-success is normal and never a red flag.

Yes — the adversary may place it inside one block. Your contradiction argument must therefore cover that case too (pumping there changes only one count, still breaking equality).

Sometimes — via Closure properties of CFLs, intersecting a suspect language with a regular language can produce a simpler non-CFL to pump, since CFLs are closed under intersection with regular languages but not with each other.