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