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[editovat | editovat zdroj]
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“).[1] Čí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.[2][3]
Příklad[editovat | editovat zdroj]
| S | → | abc |
| S | → | aSBc |
| cB | → | Bc |
| bB | → | bb |
Tato gramatika s počátečním symbolem S generuje jazyk { anbncn : n ≥ 1 },[4] 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[editovat | editovat zdroj]
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 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:[pozn. 1]
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
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 | |
| 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 | ||
| 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[editovat | editovat zdroj]
Podobně existuje snadný postup pro převod libovolné monotonní gramatiky do Kurodovy normální formy.[7][8] 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[editovat | editovat zdroj]
Poznámky[editovat | editovat zdroj]
Reference[editovat | editovat zdroj]
V tomto článku byl použit překlad textu z článku Noncontracting grammar na anglické Wikipedii.
- ↑ Chomsky 1963, pp. 360–363 and 367.
- ↑ CHOMSKY, Noam, 1959. On certain formal properties of grammars. Information and Control 2. S. 137–167. Definice na str. 141–142. Dostupné online.
- ↑ LEVELT, Willem J. M., 2008. An Introduction to the Theory of Formal Languages and Automata. [s.l.]: John Benjamins Publishing. Dostupné online. ISBN 978-90-272-3250-2. S. 125–126.
- ↑ Mateescu a Salomaa 1997, Example 2.1, p. 188.
- ↑ Mateescu a Salomaa 1997, Theorem 2.1, p. 187.
- ↑ Hopcroft a Ulman 1979, Exercise 9.9, p. 230.
- ↑ KURODA, Sige-Yuki. Classes of languages and linear-bounded automata. Information and Control. June 1964, roč. 7, čís. 2, s. 207–223. DOI 10.1016/s0019-9958(64)90120-2.
- ↑ Mateescu a Salomaa 1997, Theorem 2.2, p. 190.
Literatura[editovat | editovat zdroj]
- BOOK, R. V., 1973. On the structure of context-sensitive grammars. International Journal of Computer & Information Sciences. Roč. 2, čís. 2, s. 129–139. DOI 10.1007/BF00976059. S2CID 31699138.
- MATEESCU, Alexandru; SALOMAA, Arto, 1997. Handbook of Formal Languages. Volume I: Word, language, grammar. [s.l.]: Springer-Verlag. ISBN 3-540-61486-9. Kapitola 4: Aspects of Classical Language Theory, s. 175–252.
- HOPCROFT, John E.; ULLMAN, Jeffrey D., 1979. Introduction to Automata Theory, Languages, and Computation. [s.l.]: Addison-Wesley. Dostupné online. ISBN 0-201-02988-X.
- NOAM, Chomsky, 1963. Handbook of Mathematical Psychology. New York: Wiley. Dostupné online. S. 323–418.