Regularna gramatika

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

1. A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
2. A → aB - gde su A i B iz N i a je iz Σ
3. A → ε - gde je A iz N i ε je prazna niska, tj. niska dužine 0.

U levo-linearnoj gramatici (koja se još zove leva regularna gramatika), su sva pravila oblika:

1. A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
2. A → Ba - gde su A i B iz N i a je iz Σ
3. A → ε - gde je A iz N i ε je prazna niska.

Primer desno-linearne gramatike G sa N = {S, A}, Σ = {a, b, c}, P se sastoji od sledećih pravila:

S → aS

S → bA

A → ε

A → cA

i S je početni simbol. Ova gramatika opisuje isti jezik kao i regularni izraz a*bc*.

Regularna gramatika je levo-linearna ili desno-linearna regularna gramatika.

Neki udžbenici ne dopuštaju upotrebu praznih pravila (ε-pravila) i pretpostavljaju da prazna niska nije prisutna u jezicima.

Proširena regularna gramatika

Proširena desno-linearna gramatika je ona u kojoj su sva pravila oblika:

1. A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
2. A → wB - gde su A i B iz N i w je iz Σ^*
3. A → ε - gde je A iz N i ε je prazna niska.

Neki autori ovaj tip gramatike zovu desno-linearna gramatika, a tip iznad strogo desno-linearna gramatika. Proširena levo-linearna gramatika je ona u kojoj su sva pravila oblika:

1. A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
2. A → Bw - gde su A i B iz N i w je iz Σ^*
3. A → ε - gde je A iz N i ε je prazna niska.

Neki autori ovaj tip gramatike zovu levo-linearna gramatika, a tip iznad strogo levo-linearna gramatika.

Izražajna moć

(Strogo) levo-linearna gramatika generiše tačno onaj jezik koji prihvata nederministički konačni automat, jer postoji direktna 1-1 veza između pravila ove gramatike i automata. Dakle, svi regularni jezici su generisani levo-linearnim gramatikama. Desno-linearne gramatike opisuju jezike koji su nastali obrtanjem svih ovih jezika, i to su, takođe, regularni jezici.

Svaka strogo desno-linearna gramatika je poširena desno-linearna, dok svaka proširena desno-linearna gramatika može postati stoga tako što joj se dodaju nezavršni simboli i tada rezultat generiše isti jezik. Dakle, i proširene desno-linearna gramatike generišu regularne jezike. Analogno, isto važi za proširene levo-linearne gramatike.

Ukoliko ε-pravila nisu dozvoljena, moguće je generisati samo regularne jezike koji ne sadrže praznu nisku.

Mešanje levih i desnih regularnih pravila

Svaka linearna gramatika se može lako zapisati u obliku u kome se koristi samo kombinacija desnih i levih regularnih pravila. Regularne gramatike mogu sadržati ili levo-linearna ili desno-linearna pravila, ali ne i oba istovremeno. One generišu samo manji podskup jezika zvan regularni jezici.

Na primer, gramtika G sa N = {S, A}, Σ = {a, b}, gde je S početni simbol, i pravilima P oblika:

S → aA

A → Sb

S → ε

generiše $\{a^{i}b^{i}:i\geq 0\}$, i ovaj jezik nije regularan.

Vidi još

• Formalana gramatika
• Hijerarhija Čomskog