Razlika između inačica stranice »Deterministička kontekstno neovisna gramatika«
m (Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)) |
m (brisanje nepotrebnih znakova) |
||
| Redak 1: | 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 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). | 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). | ||
Trenutačna izmjena od 02:06, 14. ožujka 2022.
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. | |||