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 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 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 s 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
Wikiwand - on
Seamless Wikipedia browsing. On steroids.