WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

2021-11-18T01:43:20Z

Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

←Starija inačica		Inačica od 18. studeni 2021. u 01:43
Redak 37:		Redak 37:
	{{izvori}}		{{izvori}}

	*{{~~cite book~~		*{{Citiranje knjige
	\| author = Siniša Srbljić		\| author = Siniša Srbljić
	\| title = Jezični procesori 1		\| title = Jezični procesori 1

WikiSysop: Bot: Automatski unos stranica

2021-08-20T01:03:51Z

Bot: Automatski unos stranica

Nova stranica

U [[računarstvo|računarstvu]], '''regularna gramatika''' (još i '''pravilna gramatika'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 785</ref>) je '''desna regularna gramatika''' ili '''desno-linearna gramatika''' ako je [[formalna gramatika]] (''N'', Σ, ''P'', ''S'') kojoj su sve produkcije iz skupa ''P'' oblika:
# ''A'' → ''a'' - gdje je ''A'' [[završni i nezavršni znakovi|nezavršni znak]] u ''N'' i ''a'' je [[završni i nezavršni znakovi|završni znak]] u Σ
# ''A'' → ''aB'' - gdje su ''A'' i ''B'' u ''N'' i ''a'' je u Σ
# ''A'' → ε - gdje je ''A'' u ''N'' i ε označava [[prazni niz]], tj. niz duljine 0.

U '''lijevoj regularnoj gramatici''' ili '''lijevo-linearnoj gramatici''' su sve produkcije oblika:
# ''A'' → ''a'' - gdje je ''A'' nezavršni znak u ''N'' i ''a'' je završni znak u Σ
# ''A'' → ''Ba'' - gdje su ''A'' i ''B'' u ''N'' i ''a'' je u Σ
# ''A'' → ε - gdje je ''A'' u ''N'' i ε je prazni niz.

Primjer desno-linearne gramatike je ''G'' sa ''N'' = {S, A}, Σ = {a, b, c}, ''P'' se sastoji od sljedećih produkcija:
: S → aS
: S → bA
: A → ε
: A → cA
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.

== Uvod ==

Regularne gramatike opisuju točno sve [[regularni jezik|regularne jezike]] i u tom su smislu istovjetne [[konačni automat|konačnim automatima]] i [[regularni izraz|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 neovisni jezik|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 jezik|regularni jezici]].
U tom su smislu one istovjetne sa [[konačni automat|konačnim automatima]] i [[regularni izraz|regularnim izrazima]]. Kao ilustraciju možemo navesti kanonski primjer kontekstno neovisnog jezika za svim nizovima znakova oblika <math>a^ib^i</math> kojeg generira gramatika ''G'' sa ''N'' = {S, A}, Σ = {a, b}, te produkcijama u ''P'':
: S → aA
: A → Sb
: S → ε
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.

== Izvori ==

{{izvori}}

*{{cite book
| author = Siniša Srbljić
| title = Jezični procesori 1
| publisher = Element
| year = 2003
| id = {{ISBN|953-197-129-3}}}}

{{Formalni jezici i gramatike}}

[[Kategorija:Formalni jezici]]

Regularna gramatika - Povijest promjena

WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

WikiSysop: Bot: Automatski unos stranica