Vidi kôd stranice Deterministička kontekstno neovisna gramatika

<!--'''Deterministička kontekstno neovisna gramatika'''-->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 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>

== Vidi još ==
*[[Deterministički potisni automat]] (vidi formalnu definiciju zahtjeva za determinizmom).

== Izvori ==
{{izvori}}

{{Mrva-rač}}

{{Formalni jezici i gramatike}}
[[Kategorija:Formalni jezici]]