Kontekstno nezavisni jezik

Izvor: Wikipedia

U formalnoj teoriji jezika, kontekstno slobodni jezik je jezik koji generiše neka kontekstno-slobodna gramatika. Skup svih kontekstno slobodnih jezika je identičan skupu jezika koje prihvataju potisni automati.

Primeri[uredi - уреди]

Klasičan primer kontekstno slobodnog jezika je L = \{a^nb^n:n\geq1\}, jezik svih nepraznih niski parne dužine, čije ja prva polovina sastavljena od slova a, a druga polovina je sastavljena od slova b. L je generisan gramatikom S\to aSb ~|~ ab, a prihvata ga potisni automat M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, \{q_f\}) gde je \delta definisano na sledeći način:

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

\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})
where z je početni simbol steka a x predstavlja akciju skidanja sa steka.

Kontekstno slobodni jezici imaju mnoge primene u programskim jezicima; na primer, jezik svih ispravno uparenih zagrada je generisan gramatikom S\to SS ~|~ (S) ~|~ \lambda. Takođe, većina aritmetičkih izraza su generisani kontekstno slobodnim gramatikama.


Svojstva zatvorenja[uredi - уреди]

Kontekstno slobodni jezici su zatvoreni u odnosu na sledeće operacije. To jest, ako su -{L}- i -{P}- kontekstno slobodni jezici, a -{D}- je regularan jezik, onda su i sledeći jezici kontekstno-slobodni:

Kontekstno slobodni jezici nisu zatvoreni za komplement, presek i razliku.

Nezatvorenost u odnosu na presek[uredi - уреди]

Kontekstno slobodni jezici nisu zatvoreni za presek. Ovo se može videti ako se uzmu jezici A = \{a^m b^n c^n \mid m, n \geq 0 \} i B = \{a^n b^n c^m \mid m,n \geq 0\}, koji su oba konetksno slobodna. Njihov presek je A \cap B = \{ a^n b^n c^n \mid n \geq 0\}, za šta se može pokazati da nije kontekstno slobodan jezik pamping lemom za kontekstno slobodne jezike.

Svojstva odlučivosti[uredi - уреди]

Sledeći problemi su neodlučivi za proizvoljne kontekstno slobodne gramatike -{A}- i -{B}-:

  • Ekvivalencija: da li je L(A)=L(B)?
  • da li je L(A) \cap L(B) = \emptyset  ?
  • da li je L(A)=\Sigma^* ?
  • da li je L(A) \subseteq L(B) ?

Sledeći problemi su odlučivi za proizvoljne kontekstno slobodne gramatike:

  • da li je L(A)=\emptyset?
  • da li je L(A) konačan?
  • Pripadnost: za svaku datu reč w, da li je w \in L(A) ? (problem pripadnosti je čak odlučiv u polinomijalnom vremenu - videti -{algoritam CYK}-)

Svojstva kontekst-slobodnih jezika[uredi - уреди]

Reference[uredi - уреди]

  • Seymour Ginsburg (1966). The Mathematical Theory of Context-Free Languages. New York, NY, USA: McGraw-Hill, Inc.. 
  • Michael Sipser]] (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Chapter 2: Context-Free Languages, pp.91–122.
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.