Massimo Caliman
Massimo Caliman
~1 min read

Categories

  • Theoretical Computer Science

Tags

  • Theoretical Computer Science
  • CFG
  • Pumping Lemma

Languages

  • Italian

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

  1. |vwx|≤n
  2. |vx|>0
  3. ∀ 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