Kontekstno neovisni jezik

Izvor: Wikipedija
Skoči na: orijentacija, traži

Kontekstno neovisni jezik (rjeđe još i kontekstno slobodni jezik ili jezik neovisan o sadržaju, te još i bezokolinski jezik[1]) je formalni jezik koji je element skupa jezika kojeg definiraju kontekstno neovisne gramatike. Skup kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju potisni automati.

Primjeri[uredi VE | uredi]

Kanonski primjer kontekstno neovisnog jezika jest L = \{a^nb^n:n\geq1\}, jezik svih nepraznih nizova znakova (simbola) parne duljine, čiju prvu polovicu čine znakovi a, dok drugu polovicu čine znakovi b. L generira gramatika S\to aSb ~|~ ab te prihvaća potisni automat M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\}) gdje je funkcija prijelaza \delta definirana na sljedeći način:

\delta(q_0, a, z) = (q_0, a)
\delta(q_0, b, ax) = (q_1, x)
\delta(q_1, b, ax) = (q_1, x)
\delta(q_1, b, bz) = (q_f, z)

Kontekstno neovisni jezici imaju mnoge primjene u programskim jezicima; na primjer - jezik svih pravilno uparenih zagrada generira gramatika S\to SS ~|~ (S) ~|~ \lambda. Također, većinu aritmetičkih izraza mogu generirati kontekstno neovisne gramatike.

Svojstva zatvorenosti[uredi VE | uredi]

Kontekstno neovisni jezici su zatvoreni nad sljedećim operacijama. To jest, ako su L i P kontekstno neovisni jezici i D je regularni jezik, sljedeći jezici su također kontekstno neovisni:

  • Kleeneov operator L^* nad jezikom L
  • homeomorfizam φ(L) jezika L
  • nadovezivanje (konkatenacija) L \circ P jezika L i jezika P
  • unija L \cup P jezika L i jezika P
  • presjek (sa regularnim jezikom) L \cap D jezika L i jezika D

Kontekstno neovisni jezici nisu zatvoreni nad operacijama komplementa, presjeka i razlike.

Izvori[uredi VE | uredi]

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 234
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.