Lema o napihovanju za kontekstno neodvisne jezike/Dokaz

Iz MaFiRaWiki

V dokazu uporabljamo gramatiko G = < V,T,P,S > v normalni obliki po Chomskem za jezik L − {ε}. Prvi korak v dokazu je izpeljava dejstva, da iz A \in V, A \Longrightarrow^* z \in T ter | Z | "veliko" sledi, da A-drevo z rezultatom z vsebuje "dolgo" vejo. To je najlažje dokazati v obliki trditve, da je dolžina rezultata z \in T^* A-drevesa, kjer imajo vse veje manj ali enako k povezav, manjša ali enaka 2k − 1. Na tem mestu ugotovimo, da je število povezav na neki veji enako številu nekončnih vozlišč. Dokaz je zgrajen z indukcijo po k. Pri k = 1 ima A-drevo obliko, ki jo prikazuje slika 1. To sledi iz posebne oblike produkcij v normalni obliki po Chomskem. Torej smo trditev o dolžini rezultata pri k = 1 preverili. Sedaj pa naj trditev drži za vsa števila, manjša od k in dokažimo veljavnost za k. Podano je A-drevo z rezultatom z \in T^* in lastnostjo, da vsaka veja vsebuje manj ali enako k > 1 nekončnih vozlišč oziroma povezav. Zaradi oblike produkcij v gramatiki, ki je v normalni obliki po Chomskem, ima drevo obliko, kot jo prikazuje slika 2. Koren ustreza produkciji A \longrightarrow BC. Lahko zapišemo z = z1z2, pri čemer sta z1 in z2 rezultata nekega B- oziroma C-drevesa. Prikazano B- in C-drevo ima na vsaki veji manj ali enako k − 1 nekončnih vozlišč in na podlagi induktivne predpostavke ugotovimo, da velja |z_1|,|z_2|\leq 2^{k-2}, iz česar izpeljemo |z|=|z_1z_2|\leq 2 \cdot 2^{k-2} = 2^{k-1}.
Sedaj pa naj bo k številonekončnih simbolov v G in naj bo konstanta n iz trditve v lemi enaka 2k. Naj velja z \in L(G) in |z| \geq n. Na podlagi pravkar dokazanega v tem primeru sklepamo, da obstaja v drevesu izpeljav besede z neka veja z več kot k nekončnimi vozlišči. Opazujmo tako vejo in ji sledimo od končnega vozlišča proti korenu. Na tej poti se neki nekončni simbol mora ponoviti (to sledi iz števila nekončnih simbolov v V in števila nekončnih simbolov na veji). Ustavimo se pri prvem ponovljenem simbolu, denimo A. Besede u, v, w, x, y ustrezajo delom rezultata z. Sedaj pa dokažimo lastnosti iz leme. |vx| \geq 1 sledi iz dejstva, da je dolžina vx najmanjša v primeru, ko zgornjemu simbolu A ustreza produkcija A \longrightarrow AB ali A \longrightarrow BA oziroma, ko je spodnji simbol A pravzaprav naslednik zgornjega A in pa ko je naslednik B končen simbol. V tem primeru je | vx | = 1, sicer je vx daljše.
|vwx| \leq n sledi iz naslednjega premisleka: |w| \leq 2^{k-1}, ker pod spodnjim simbolom A ni ponavljanja nekončnih simbolov; iz istega razloga je skupna dolžina besed v in x tudi \leq 2^{k-1}.
\forall i \geq 0: uv^iwx^iy \in L(g) pa sledi iz dejstva, da lahko spodnje A-drevo zamenjamo z zgornjim poljubno mnogokrat (to ustreza primerom i \geq 1) oziroma zgornje s spodnjim (i = 0).

slika 1: A-drevo višine 1


slika 2: A-drevo, ki ustreza k > 1

Osebna orodja