Kontekstno neovisni jezik

Izvor: Wikipedija

Kontekstno neovisni jezik (rjeđe još i kontekstno slobodni jezik ili jezik neovisan o sadržaju) 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.

[uredi] Primjeri

Kanonski primjer kontekstno neovisnog jezika jest , jezik svih nepraznih nizova znakova (simbola) parne duljine, čiju prvu polovicu čine znakovi a, dok drugu polovicu čine znakovi b. L generira gramatika te prihvaća potisni automat M = ({q₀,q₁,q_f},{a},{a,b,z},δ,q₀,{q_f}) gdje je funkcija prijelaza δ definirana na sljedeći način:

δ(q₀,a,z) = (q₀,a)
δ(q₀,b,ax) = (q₁,x)
δ(q₁,b,ax) = (q₁,x)
δ(q₁,b,bz) = (q_f,z)

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

[uredi] Svojstva zatvorenosti

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) jezika L i jezika P
• unija jezika L i jezika P
• presjek (sa regularnim jezikom) jezika L i jezika D

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

[uredi] Reference

• Michael Sipser (1997). Introduction to the Theory of Computation, PWS Publishing. ISBN 0-534-94728-X.
• Siniša Srbljić (2003). Jezični procesori 1, Element. ISBN 953-197-129-3.

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.