Kleeneliness is next to Gödeliness
Lemma
Given $L$ is a Context-Free (CF) language, there exists a constant $n \in \mathbb{N}$ such that for all $z \in L$ with $\vert z \vert \ge n$, we can decompose $z = uvwxy$ satisfying:
- $\vert vwx \vert \le n$
- $\vert vx \vert > 0$
- $\forall i \ge 0$, we have that $uv^iwx^iy \in L$
Usage
The lemma is used to prove that a language is not CF. To do so, one must show that for an arbitrary $n$, there exists $z \in L$ with $\vert z \vert \ge n$ such that for every possible decomposition $uvwxy$ satisfying constraints 1 and 2, $uv^iwx^iy \notin L$ for some $i \ge 0$.