Monotonní gramatika

V teorii formálních jazyků je gramatika monotonní, pokud všechna její přepisovací pravidla jsou tvaru α → β, kde α a β jsou řetězce neterminálních a terminálních symbolů, v nichž délka řetězce α je menší nebo rovna délce řetězce β, |α| ≤ |β|, tj. β není kratší než α. Gramatika je v zásadě monotonní, pokud může obsahovat pravidlo S → ε, kde S je počáteční symbol a ε prázdný řetězec; pokud gramatika toto pravidlo obsahuje, S se nesmí objevit na pravé straně žádného pravidla.

Použitím žádného z pravidel monotonní gramatiky se nezkrátí délka řetězce. Pokud gramatika má pouze pravidla, která striktně zvětšují délku řetězce, mluvíme o rostoucí kontextové gramatice.

Historie

Chomsky (1963) nazývá monotonní gramatiky gramatikami typu 1; ve stejné práci nazývá kontextové gramatiky „gramatikami typu 2“, a dokázal, že tyto dvě definice jsou slabě ekvivalentní (bezkontextové gramatiky byly v této práci označovány za „typ 4“). Číslování gramatik v této Chomského práci z roku 1963 se liší od číslování použitého v popisu hierarchie jazyků, známé dnes jako Chomského hierarchie, protože Chomsky se snažil zdůraznit rozdíl mezi slabou [generativní] a silnou [strukturální] ekvivalencí; ve své práci z roku 1959 používal označení „gramatiky typu 1“ pro kontextové gramatiky a „gramatiky typu 2“ pro bezkontextové gramatiky.

Příklad

S	→	abc
S	→	aSBc
cB	→	Bc
bB	→	bb

Tato gramatika s počátečním symbolem S generuje jazyk {{nowrap|1={ anbncn : n ≥ 1 } }}, který není bezkontextový, jak lze dokázat pomocí pumping lemmatu pro bezkontextové jazyky.

Kontextová gramatika pro stejný jazyk je ukázána #Transformace na kontextovou gramatiku|níže.

Transformace na kontextovou gramatiku

Každou monotonní gramatiku (N, Σ, P, S) lze transformovat na kontextovou gramatiku (N’, Σ, P’, S) takto: # Pro každá terminální symbol a ∈ Σ, zavedeme nový neterminální symbol [a] ∈ N’, a nové pravidlo ([a] → a) ∈ P’. # Ve všech pravidlech z množiny P, nahradíme každý terminální symbol a jemu odpovídajícím neterminálním symbolem [a]. +more Díky tomu všechna tato pravidla přejdou na tvar X1. Xm → Y1. Yn pro neterminály Xi, Yj a m≤n. # Každé pravidlo X1. Xm → Y1. Yn, kde m>1 nahradíme celkem 2m pravidly: ::

X1	X2	.	Xm-1	Xm				→	Z1	X2	.	Xm-1	Xm
Z1	X2	.	Xm-1	Xm				→	Z1	Z2	.	Xm-1	Xm
								:
Z1	Z2	.	Xm-1	Xm				→	Z1	Z2	.	Zm-1	Xm
Z1	Z2	.	Zm-1	Xm				→	Z1	Z2	.	Zm-1	Zm
Z1	Z2	.	Zm-1	Zm	Ym+1	.	Yn	→	Y1	Z2	.	Zm-1	Zm
Y1	Z2	.	Zm-1	Zm	Ym+1	.	Yn	→	Y1	Y2	.	Zm-1	Zm
								:
Y1	Y2	.	Zm-1	Zm	Ym+1	.	Yn	→	Y1	Y2	.	Ym-1	Zm
Y1	Y2	.	Ym-1	Zm	Ym+1	.	Yn	→	Y1	Y2	.	Ym-1	Ym

::kde každé Zi ∈ N’ je nový neterminální symbol, který se neobjevuje nikde jinde.

Například #Příklad|výše uvedenou monotonní gramatiku generující jazyk { anbncn | n ≥ 1 } lze převést na následující kontextovou gramatiku s počátečním symbolem S, která generuje stejný jazyk:

	[a]	→	a				z kroku 1
	[b]	→	b				z kroku 1
	[c]	→	c				z kroku 1
	S	→	[a]	[b]	[c]		z kroku 2, nezměněno
	S	→	[a]	S	B	[c]	z kroku 2, nezměněno
[c]	B	→	B	[c]			z kroku 2, dále změněno níže
[c]	B	→	Z1	B			změněno z výše uvedeného v kroku 3
Z1	B	→	Z1	Z2			změněno z výše uvedeného v kroku 3
Z1	Z2	→	B	Z2			změněno z výše uvedeného v kroku 3
B	Z2	→	B	[c]			změněno z výše uvedeného v kroku 3
[b]	B	→	[b]	[b]			z kroku 2, dále změněno níže
[b]	B	→	Z3	B			změněno z výše uvedeného v kroku 3
Z3	B	→	Z3	Z4			změněno z výše uvedeného v kroku 3
Z3	Z4	→	[b]	Z4			změněno z výše uvedeného v kroku 3
[b]	Z4	→	[b]	[b]			změněno z výše uvedeného v kroku 3

Expresivní síla

Podobně existuje snadný postup pro převod libovolné monotonní gramatiky do Kurodovy normální formy. Naopak, každá kontextová gramatika a každá gramatika v Kurodově normální formě je triviálně také monotonní gramatikou. +more Proto monotonní gramatiky, gramatiky v Kurodově normální formě, a kontextové gramatiky mají stejný expresivní sílu. Přesněji, monotonní gramatiky popisují právě kontextové jazyky, které neobsahují prázdný řetězec, zatímco v zásadě monotonní gramatiky popisují právě množinu kontextových jazyků.

Odkazy

Poznámky

Reference

Literatura

Související články

Kontextová gramatika * Rostoucí kontextová gramatika * Kurodova normální forma

Kategorie:Formální jazyky