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 , který není bezkontextový, jak lze dokázat pomocí pumping lemmatu pro bezkontextové jazyky.
Kontextová gramatika pro stejný jazyk je ukázána 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]. Díky tomu všechna tato pravidla přejdou na tvar → pro neterminály Xi, Yj a m≤n. Každé pravidlo → , 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 || Ym+1 || … || Yn |- | Z1 || Z2 || … || Zm-1 || Zm || Ym+1 || … || Yn || → || Y1 || Z2 || … || Zm-1 || Zm || Ym+1 || … || Yn |- | Y1 || Z2 || … || Zm-1 || Zm || Ym+1 || … || Yn || → || Y1 || Y2 || … || Zm-1 || Zm || Ym+1 || … || Yn
| Y1 || Y2 || … || Zm-1 || Zm || Ym+1 || … || Yn || → || Y1 || Y2 || … || Ym-1 || Zm || Ym+1 || … || Yn |- | Y1 || Y2 || … || Ym-1 || Zm || Ym+1 || … || Yn || → || Y1 || Y2 || … || Ym-1 || Ym || Ym+1 || … || Yn |} kde každé Zi ∈ N’ je nový neterminální symbol, který se neobjevuje nikde jinde.
Napří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. 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