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“).[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

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

Každou monotonní gramatiku (N, Σ, P, S) lze transformovat na kontextovou gramatiku (N’, Σ, P’, S) takto:

  1. Pro každá terminální symbol a ∈ Σ, zavedeme nový neterminální symbol [a] ∈ N’, a nové pravidlo ([a] → a) ∈ P’.
  2. 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.
  3. Každé pravidlo X1...Xm → Y1...Yn, kde m>1 nahradíme celkem 2m pravidly:[pozn. 1]
X1X2...Xm-1 Xm→Z1X2...Xm-1 Xm
Z1X2...Xm-1 Xm→Z1Z2...Xm-1 Xm
:
Z1Z2...Xm-1 Xm→Z1Z2...Zm-1 Xm
Z1Z2...Zm-1 Xm→Z1Z2...Zm-1 ZmYm+1...Yn
Z1Z2...Zm-1 ZmYm+1...Yn      →      Y1Z2...Zm-1 ZmYm+1...Yn
Y1Z2...Zm-1 ZmYm+1...Yn→Y1Y2...Zm-1 ZmYm+1...Yn
:
Y1Y2...Zm-1 ZmYm+1...Yn→Y1Y2...Ym-1 ZmYm+1...Yn
Y1Y2...Ym-1 ZmYm+1...Yn→Y1Y2...Ym-1 YmYm+1...Yn
kde každé Zi ∈ N’ je nový neterminální symbol, který se neobjevuje nikde jinde.[5][6][pozn. 2]

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]→az kroku 1
[b]→bz kroku 1
[c]→cz kroku 1
S→[a][b][c]z kroku 2, nezměněno
S→[a]SB[c]      z kroku 2, nezměněno
[c]B→B[c]z kroku 2, dále změněno níže
[c]B→Z1Bzměněno z výše uvedeného v kroku 3
Z1B→Z1Z2změněno z výše uvedeného v kroku 3
Z1Z2      →      BZ2změněno z výše uvedeného v kroku 3
BZ2→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→Z3Bzměněno z výše uvedeného v kroku 3
Z3B→Z3Z4změněno z výše uvedeného v kroku 3
Z3Z4→[b]Z4změ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.[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

Poznámky

  1. ↑ Pro usnadnění je přepisovaná (nekontextová) část levé a pravé strany zvýrazněna polotučným písmem.
  2. ↑ Ve vydání z roku 2003 chybí kapitola o monotonních a kontextových jazycích.

Reference

V tomto článku byl použit překlad textu z článku Noncontracting grammar na anglické Wikipedii.

  1. ↑ Chomsky 1963, pp. 360–363 and 367.
  2. ↑ CHOMSKY, Noam, 1959. On certain formal properties of grammars. Information and Control 2. S. 137–167. Definice na str. 141–142. Dostupné online. 
  3. ↑ 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. 
  4. ↑ Mateescu a Salomaa 1997, Example 2.1, p. 188.
  5. ↑ Mateescu a Salomaa 1997, Theorem 2.1, p. 187.
  6. ↑ Hopcroft a Ulman 1979, Exercise 9.9, p. 230.
  7. ↑ 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. 
  8. ↑ Mateescu a Salomaa 1997, Theorem 2.2, p. 190.

Literatura

  • 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. 

Související články