Razlika između inačica stranice »Deterministička kontekstno neovisna gramatika«

Inačica od 07:11, 16. studenoga 2021.

U jezikoslovlju i računarstvu, deterministička kontekstno neovisna gramatika (DKNG) je pravi podskup kontekstno neovisne gramatike. Determinističke kontekstno neovisne gramatike su one koje može prepoznati deterministički potisni automat.

Od posebne su važnosti u polju računarstva s obzirom da mogu biti učinkovito prepoznate, dok nedeterminističke kontekstno neovisne gramatike zahtijevaju znatno složenije programe i potencijalno veći trošak vremenskih i prostornih resursa - za svaki nedeterministički korak stog se mora kopirati i propagirati. U praksi parseri (poput onih koje generira YACC), čak i ako su nedeterministički, su pretvoreni u determinističke dodatkom ograničavanja poput prednosti (engl. precedence).

Deterministički kontekstno neovisni jezici su pravi podskup jezika koji ima nejednoznačnu kontekstno neovisnu gramatiku. Postoje i jezici sa nejednoznačnom kontekstno neovisnom gramatikom, poput S → 0S0 | 1S1 | ε, koja je nejednoznačna i definira jezik palindroma binarne abecede, i koji su očito parsabilni determinističkim potisnim automatom. ^[1]

Vidi još

Deterministički potisni automat (vidi formalnu definiciju zahtjeva za determinizmom).

Izvori

↑ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. str. 246-253

Nedovršeni članak Deterministička kontekstno neovisna gramatika 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.

[1] Hopcroft, John; Rajeev Motwani & Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. str. 246-253

[1]

@@ Redak 3: / Redak 3: @@
 Od posebne su važnosti u polju računarstva s obzirom da mogu biti učinkovito prepoznate, dok nedeterminističke kontekstno neovisne gramatike zahtijevaju znatno složenije programe i potencijalno veći trošak vremenskih i prostornih resursa - za svaki nedeterministički korak stog se mora kopirati i propagirati. U praksi [[parser]]i (poput onih koje generira [[YACC]]), čak i ako su nedeterministički, su pretvoreni u determinističke dodatkom ograničavanja poput prednosti (engl. precedence).
-Deterministički kontekstno neovisni jezici su pravi podskup jezika koji ima [[nejednoznačna gramatika|nejednoznačnu kontekstno neovisnu gramatiku]]. Postoje i jezici sa nejednoznačnom kontekstno neovisnom gramatikom, poput S → 0S0 | 1S1 | ε, koja je nejednoznačna i definira jezik [[palindrom]]a binarne abecede, i koji su očito [[parser|parsabilni]] 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 = 246-253 }} </ref>
+Deterministički kontekstno neovisni jezici su pravi podskup jezika koji ima [[nejednoznačna gramatika|nejednoznačnu kontekstno neovisnu gramatiku]]. Postoje i jezici sa nejednoznačnom kontekstno neovisnom gramatikom, poput S → 0S0 | 1S1 | ε, koja je nejednoznačna i definira jezik [[palindrom]]a binarne abecede, i koji su očito [[parser|parsabilni]] 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 = 246-253 }} </ref>
 == Vidi još ==