Deterministički kontekstno neovisni jezik je formalni jezik koji je pravi podskup skupa svih jezika koje definiraju kontekstno neovisne gramatike. Skup svih determinističkih kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju deterministički potisni automati.
Deterministički kontekstno neovisni jezici su pravi podskup jezika koji posjeduju nejednoznačne kontekstno neovisne gramatike. Postoje i jezici s nejednoznačnim kontekstno neovisnim gramatikama, poput S → 0S0 | 1S1 | ε, koja je nejednoznačna i definira samo jezik palindroma binarne abecede, te se razvidno i ne može parsirati determinističkim potisnim automatom.
Jezici iz ove klase imaju veliku praktičnu važnost u računarstvu. Složenost programa i izvršavanja determinističkog potisnog automata je znatno manja od nedeterminističkog koji mora činiti kopije stoga za svaki nedeterministički korak. Zbog praktičnih razloga prevoditelji implementiraju gramatike za determinističke jezike. U nekim slučajevima je parser izgrađen za gramatiku koja nije deterministička, ali je modificirana dodatnim ograničenjima, poput prednosti (operatora), kako bi postala deterministička.
Izvori
Kategorija:Formalni jezici