Deterministički kontekstno neovisni jezik: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
m Bot: ispravka HTML koda i wiki sintakse |
još malo |
||
Redak 1:
'''Deterministički kontekstno neovisni jezik''' je [[formalni jezik]] koji je pravi [[podskup]] skupa svih jezika koje definiraju kontekstno neovisne gramatike.<ref> {{cite book | last = [[John Hopcroft|Hopcroft]] | first = John | coauthors = [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] | year = 1979 | publisher = Addison-Wesley | pages = 233 }} </ref> Skup svih determinističkih kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju [[deterministički potisni automat|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 [[palindrom]]a binarne abecede, te se razvidno i ne može [[parser|parsirati]] determinističkim potisnim automatom. <ref> {{cite book | last = [[John Hopcroft|Hopcroft]] | first = John | coauthors = [[Rajeev Motwani]] & [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] 2nd edition | year = 2001 | publisher = Addison-Wesley | pages = 249-253 }} </ref>
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.
== Reference ==
| |||