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 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.[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.

Izvori

uredi
  1. Hopcroft, John; Ullman, Jeffrey. 1979. Introduction to automata theory, languages, and computation. Addison-Wesley. str. 233
  2. Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. 2001. Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. str. 249–253
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.