Deterministička kontekstno neovisna gramatika

Izvor: Wikipedija
Skoči na: orijentacija, traži

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š[uredi VE | uredi]

Izvori[uredi VE | uredi]

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


Computer-aj aj ashton 01.svg Nedovršeni članak Deterministička kontekstno neovisna gramatika koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.


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.