Deterministički kontekstno neovisni jezik

Deterministički kontekstno neovisni jezik je formalni jezik koji je pravi podskup skupa svih jezika koje definiraju kontekstno neovisne gramatike.[1] 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 sa 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. [2]

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.

IzvoriUredi


  Nedovršeni članak Deterministički kontekstno neovisni jezik koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.


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.