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