Lema o napihovanju za kontekstno neodvisne jezike

Iz MaFiRaWiki


	Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili. Kaj pomeni to opozorilo?

Naj bo dan kontekstno neodvisni jezik L. Potem obstaja neka konstanta n, ki je odvisna le od jezika L, tako da velja: poljubno besedo $z \in L$ , za katero velja $|z| \geq n$ , lahko predstavimo v obliki $z = u v w x y$ , pri čemer velja $|vwx| \leq n$ , $|vx| \geq 1$ in za vse $i \geq 0$ velja $uv^iwx^iy \in L$ .

[spremeni]

Dokaz

[spremeni]

Primer

Lemo o napihovanju največkrat uporabljamo pri dokazovanju tega, da nek jezik ni kontekstno-neodvisen. Na primer, jezik $L = \{a^nb^nc^n| n\in\mathbb{N}\}$ ni kontekstno-neodvisen, kar dokažemo takole:

Recimo, da je L kontekstno-neodvisen. Potem zanj velja lema:
1. $|vxy| \leq p$ . To pomeni, da srednji del besede uvxyz ni predolg.
2. $vy \ne \epsilon$ . Ker sta v in y dela, ki jih bomo “napihnili”, ta pogoj pove, da mora biti vsaj en od nizov, ki jih bomo napihnili, neprazen.
3. $\forall i \geq 0: uv^ixy^iz \in L$ . To pomeni, da lahko niza v in y "napihnemo" kolikokrat hočemo,
  vključno z 0, pa bo rezultat še vedno v jeziku L.
Če je niz $w \in L$ , kjer $| w | > p$ , sledi: $w = u v x y z$ , kjer $|vxy| \leq p$
Zdaj izberimo vrednost za n, ki je večja od p.
Potem, kakorkoli iz vxy pridemo do niza oblike $a n b n c n$ , vxy ne more vsebovati več kot dveh raličnih črk, ker sta najbolj desni a in najbolj levi c n+1 mest narazen. Beseda je lahko iz samih a-jev, b-jev, ali c-jev, lahko pa iz a-jev in b-jev, ali b-jev in c-jev. Torej niz vxy ne more vsebovati več kot dveh različnih črk, ampak po lemi ne more biti niti prazen, torej mora vsebovati vsaj eno črko.
Zdaj lahko začnemo "napihovati"
1. Ker je $uvxyz \in L$ , mora biti tudi $uv^2xy^2z \in L$ . Ker v in y ne moreta biti oba prazna,
  $| u v 2 x y 2 z | > | u v x y z |$ , torej smo nekaj črk dodali.
2. Toda ker vy ne vsebuje vseh treh možnih črk, ne more biti število dodanih posameznih črk enako. Torej napihnjena beseda $u v 2 x y 2 z$ ne more biti v L.
Prišli smo do protislovja, torej je bila predpostavka, da je jezik L kontekstno-neodvisen napačna.