Regularna gramatika

Izvor: Wikipedija

U računarstvu, desna regularna gramatika ili desno-linearna gramatika je formalna gramatika (N, Σ, P, S) kojoj su sve produkcije iz skupa P oblika:

1. A → a - gdje je A nezavršni znak u N i a je završni znak u Σ
2. A → aB - gdje su A i B u N i a je u Σ
3. A → ε - gdje je A u N i ε označava prazni niz, tj. niz duljine 0.

U lijevoj regularnoj gramatici ili lijevo-linearnoj gramatici sve produkcije su oblika:

1. A → a - gdje je A nezavršni znak u N i a je završni znak u Σ
2. A → Ba - gdje su A i B u N i a je u Σ
3. A → ε - gdje je A u N i ε je prazni niz.

Primjer desno-linearne gramatike je G sa N = {S, A}, Σ = {a, b, c}, P se sastoji od sljedećih produkcija:

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.

[uredi] Uvod

Regularne 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 sa konačnim automatima i regularnim izrazima. Kao ilustraciju možemo navesti kanonski primjer kontekstno neovisnog jezika za svim nizovima znakova oblika aⁱbⁱ kojeg generira gramatika G sa N = {S, A}, Σ = {a, b}, te produkcijama u P:

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 (ε-produkcija) i pretpostavljaju da prazni niz nije prisutan u jezicima.

[uredi] Reference

• 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.