Deterministička kontekstno neovisna gramatika: razlika između inačica

Izbrisani sadržaj Dodani sadržaj
m coauthors→last,first
m RpA: WP:NI, WP:HRV
 
Redak 1:
U [[jezikoslovlje|jezikoslovlju]] i [[računarstvo|računarstvu]], '''deterministička kontekstno neovisna gramatika''' (DKNG) je pravi podskup [[kontekstno neovisna gramatika|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 na to 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 sas 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 |last1=Hopcroft |first1=John |last2=Motwani |first2=Rajeev |last3=Ullman |first3=Jeffrey |title=Introduction to automata theory, languages, and computation 2nd edition |year=2001 |publisher=Addison-Wesley |pages=246-253 }} </ref>
 
== Vidi još ==