From Wikipedia, the free encyclopedia
U računarstvu, regularna gramatika (još i pravilna gramatika[1]) je desna regularna gramatika ili desno-linearna gramatika ako je formalna gramatika (N, Σ, P, S) kojoj su sve produkcije iz skupa P oblika:
U lijevoj regularnoj gramatici ili lijevo-linearnoj gramatici su sve produkcije oblika:
Primjer desno-linearne gramatike je G s N = {S, A}, Σ = {a, b, c}, P se sastoji od sljedećih produkcija:
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.
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 s konačnim automatima i regularnim izrazima. Kao ilustraciju možemo navesti kanonski primjer kontekstno neovisnog jezika za svim nizovima znakova oblika kojeg generira gramatika G s N = {S, A}, Σ = {a, b}, te produkcijama u P:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.