Regularna gramatika

Из Википедије, слободне енциклопедије

Regularna gramatika[уреди]

U računarstu, 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. Aa - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
  2. AaB - 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. Aa - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
  2. ABa - 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. Aa - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
  2. AwB - 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. Aa - gde je A nezavršni simbol iz N i a je završni simbol iz Σ
  2. ABw - 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^ib^i : i \geq 0\}, i ovaj jezik nije regularan.

Videti[уреди]