Massimo Caliman
by Massimo Caliman
~1 min read

Categories

  • Programming

Tags

  • Context-Free Grammar
  • Pumping Lemma

Kleeneliness is next to Gödeliness

Lemma

Given L a CF language then ∃ n∈N, n constant so that ∀ z∈L, |z|≥n so that we can decompose z=uvwxy so that 1 |vwx|≤n 2 |vx|>0 3 ∀ i≥0 we have that uvⁱwxⁱy∈L

Usage

One uses the lemma to prove that a language is not CF, to do so one must show, that fixed an arbitrary n arbitrary, ∃ zⁱwxⁱy∉L \ |z\≥n but so that for every possible decomposition such as uvwxy, with 1. and 2. constraints uvⁱwxⁱy∉L for some i≥0