Kleeneliness is next to Gödeliness
Lemma
Given $L$ a CF language, then $\exists n \in \mathbb{N}$, where $n$ is a constant such that $\forall z \in L$, $\vert z \vert \ge n$, we can decompose $z = uvwxy$ such that:
- $\vert vwx \vert \le n$
- $\vert vx \vert > 0$
- $\forall i \ge 0$, we have that $uv^iwx^iy \in L$
Usage
One uses the lemma 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$.
Revision: 2026-04-25