Deterministički kontekstno neovisni jezik: razlika između inačica

Izvor: Hrvatska internetska enciklopedija
Prijeđi na navigaciju Prijeđi na pretraživanje
Novija izmjena →
Bot: Automatski unos stranica
 
m Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)
Redak 1: Redak 1:
<!--'''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.<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]]i.
<!--'''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.<ref> {{Citiranje knjige | 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]]i.


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>
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> {{Citiranje knjige | 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.
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.

Inačica od 16. studeni 2021. u 07:11

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

  1. ↑
    • Nepoznat parametar: coauthors
  2. ↑
    • Nepoznat parametar: coauthors


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.
Dobavljeno iz "https://enciklopedija.cc/index.php?title=Deterministički_kontekstno_neovisni_jezik&oldid=330570"