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:
- 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