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.
Izvori
- ↑ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. str. 233
- ↑ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (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 uređivanja Hrvatske internetske enciklopedije.
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. |