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: A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ A → aB - gde su A i B iz N i a je iz Σ 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: A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ A → Ba - gde su A i B iz N i a je iz Σ 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: A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ A → wB - gde su A i B iz N i w je iz Σ* 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: A → a - gde je A nezavršni simbol iz N i a je završni simbol iz Σ A → Bw - gde su A i B iz N i w je iz Σ* 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 , i ovaj jezik nije regularan.
Vidi još
Formalana gramatika Hijerarhija Čomskog
Категорија:Formalni jezici