Regularna gramatika
U računarstvu, regularna gramatika (još i pravilna gramatika[1]) je desna regularna gramatika ili desno-linearna gramatika ako je formalna gramatika (N,
- A → a - gdje je A nezavršni znak u N i a je završni znak u
Σ - A → aB - gdje su A i B u N i a je u
Σ - A →
ε - gdje je A u N iε označava prazni niz, tj. niz duljine 0.
U lijevoj regularnoj gramatici ili lijevo-linearnoj gramatici su sve produkcije oblika:
- A → a - gdje je A nezavršni znak u N i a je završni znak u
Σ - A → Ba - gdje su A i B u N i a je u
Σ - A →
ε - gdje je A u N iε je prazni niz.
Primjer desno-linearne gramatike je G s N = {S, A},
- S → aS
- S → bA
- A →
ε - A → cA
S je početni nezavršni znak. Ova gramatika opisuje isti jezik kao i regularni izraz a*bc*.
Regularna gramatika je lijevo-linearna ili desno-linearna regularna gramatika.
Uvod
urediRegularne gramatike opisuju točno sve regularne jezike i u tom su smislu istovjetne konačnim automatima i regularnim izrazima. Štoviše, desno-linearne regularne gramatike su same istovjetne regularnim jezicima, baš kao što su i lijevo-linearne regularne gramatike.
Svaka regularna gramatika je kontekstno neovisna gramatika.
Svaka kontekstno neovisna gramatika se može lako zapisati u obliku u kojem je korištena samo kombinacija desnih i lijevih regularnih produkcija. Stoga takve gramatike mogu opisati sve kontekstno neovisne jezike. Regularne gramatike, koje koriste ili lijevo-linearne ili desno-linearne produkcije ali ne i obje, mogu generirati samo manji podskup jezika zvan regularni jezici.
U tom su smislu one istovjetne s konačnim automatima i regularnim izrazima. Kao ilustraciju možemo navesti kanonski primjer kontekstno neovisnog jezika za svim nizovima znakova oblika kojeg generira gramatika G s N = {S, A},
- S → aA
- A → Sb
- S →
ε
gdje je S početni nezavršni znak. Uočimo da ova gramatika ima i lijevo-linearne i desno-linearne produkcije te stoga više nije regularna.
Neki udžbenici zabranjuju uporabu praznih produkcija (
Izvori
uredi- ↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 785
- Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3
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. |