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 = uvwxy, pri čemer velja |vwx| \leq n, |vx| \geq 1 in za vse i \geq 0 velja uv^iwx^iy \in L.

Dokaz

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:

  1. 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.
  2. Če je niz w \in L, kjer | w | > p, sledi: w = uvxyz, kjer |vxy| \leq p
  3. Zdaj izberimo vrednost za n, ki je večja od p.
  4. Potem, kakorkoli iz vxy pridemo do niza oblike anbncn, 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.
  5. 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,
      | uv2xy2z | > | uvxyz | , 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 uv2xy2z ne more biti v L.
  6. Prišli smo do protislovja, torej je bila predpostavka, da je jezik L kontekstno-neodvisen napačna.

Glej tudi

Osebna orodja