Kleeneliness is next to Gödeliness
Lemma
Dato L un linguaggio CF allora ∃ n∈N, n costante tale che ∀ z∈L, |z|≥n per cui possiamo decomporre z=uvwxy in modo che
- |vwx|≤n
- |vx|>0
- ∀ i≥0 si ha che uvⁱwxⁱy∈L
Uso
Si usa il lemma per provare che un linguaggio non è CF, per farlo occorre mostrare, che fissato un n arbitrario, ∃ z∈L |z|≥n ma tale che per ogni possibile decomposizione come uvwxy, con 1. e 2. vincoli uvⁱwxⁱy∉L per qualche i≥0