Noncontracting grammar - Noncontracting grammar

v teorie formálního jazyka, a gramatika je nonkontrakční (nebo monotóní) pokud jsou všechna jeho produkční pravidla ve formě α → β, kde α a β jsou struny z neterminální a koncové symboly a délka α je menší nebo rovna délce β, | α | ≤ | β |, tj. Β, není kratší než α. Gramatika je v zásadě bez smluv pokud může existovat jedna výjimka, konkrétně pravidloS → kdekoli S je počáteční symbol a ε prázdný řetězec a dále, S nikdy se nevyskytuje na pravé straně žádného pravidla.

Žádné z pravidel nekontraktující gramatiky nezmenšuje délku přepisovaného řetězce. Pokud každé pravidlo dokonce správně zvětší délku, nazývá se gramatika a rostoucí kontextová gramatika.

Dějiny

Chomsky (1963) nazval kontraktační gramatiku a gramatika typu 1; ve stejné práci nazval a kontextová gramatika „gramatiku typu 2“ a dokázal, že tito dva jsou slabě ekvivalentní (bezkontextové gramatiky byly v této práci označeny jako „typ 4“).[1] Schéma číslování typů v této práci Chomského z roku 1963 se neshoduje s dřívějším, dnes známým jako Chomského hierarchie protože se snažil zdůraznit rozdíl mezi slabou [generativní] a silnou [strukturální] rovnocenností; ve své práci z roku 1959 použil „gramatiku typu 1“ k označení kontextové gramatiky a „typ 2“ bez kontextu.[2][3]

Příklad

S→abc
S→aSBc
cB→Před naším letopočtem
bB→bb

Tato gramatika se symbolem začátku S, generuje jazyk { AnbnCn : n ≥ 1 },[4]což není bez kontextu v důsledku čerpací lemma.

Zobrazí se kontextová gramatika pro stejný jazyk níže.

Transformace do kontextové gramatiky

Každá gramatika bez smlouvy (N, Σ, P, S) lze transformovat na a kontextová gramatika (N„, Σ, P’, S) jak následuje:

  1. Pro každý symbol terminálu A ∈ Σ, zavést nový neterminální symbol [A] ∈ N“A nové pravidlo ([A] → A) ∈ P’.
  2. V pravidlech P, vyměňte každý symbol terminálu A příslušným neterminálním symbolem [A]. Výsledkem je, že všechna tato pravidla mají formu X1...Xm → Y1...Yn pro neterminály Xi, Yj a m≤n.
  3. Vyměňte každé pravidlo X1...Xm → Y1...Yn s m> 1 krát 2m pravidla:[poznámka 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ál, který se jinde nevyskytuje.[5][6]

Například výše gramatika bez smlouvy pro { AnbnCn | n ≥ 1} vede k následující kontextově citlivé gramatice (se symbolem začátku S) pro stejný jazyk:

[A]→Aod kroku 1
[b]→bod kroku 1
[C]→Cod kroku 1
S→[A][b][C]od kroku 2, beze změny
S→[A]SB[C]      od kroku 2, beze změny
[C]B→B[C]z kroku 2, dále upraveno níže
[C]B→Z1Bupraveno shora v kroku 3
Z1B→Z1Z2upraveno shora v kroku 3
Z1Z2      →      BZ2upraveno shora v kroku 3
BZ2→B[C]upraveno shora v kroku 3
[b]B→[b][b]z kroku 2, dále upraveno níže
[b]B→Z3Bupraveno shora v kroku 3
Z3B→Z3Z4upraveno shora v kroku 3
Z3Z4→[b]Z4upraveno shora v kroku 3
[b]Z4→[b][b]upraveno shora v kroku 3

Expresivní síla

Podobně existuje snadný postup, jak přenést jakoukoli nesmluvní gramatiku Kuroda normální forma.[7][8]Naopak každá kontextově citlivá gramatika a každá gramatika Kurody v normální formě je triviálně také nekontraktující gramatika. Nekontraktující gramatiky, gramatiky v normální formě Kuroda a kontextově citlivé gramatiky mají tedy stejnou expresivní sílu. Přesněji řečeno, nekontraktující gramatiky přesně popsat kontextově citlivé jazyky , které nezahrnují prázdný řetězec, zatímco v podstatě nekontrolovatelné gramatiky přesně popisují množinu kontextově citlivé jazyky.

Viz také

Poznámky

  1. ^ Pro větší pohodlí je nekontextová část levé a pravé strany zobrazena tučně.

Reference

  1. ^ Noam Chomsky (1963). Msgstr "Formální vlastnosti gramatiky". V R. D. Luce a R. R. Bush a E. Galanter (ed.). Příručka matematické psychologie. II. New York: Wiley. str.323 –418. Zde: str. 360–363 a 367
  2. ^ Chomsky, N. 1959a. O určitých formálních vlastnostech gramatik. Informace a řízení 2: 137–67. (Definice 141–42)
  3. ^ Willem J. M. Levelt (2008). Úvod do teorie formálních jazyků a automatů. Nakladatelství John Benjamins. str. 125–126. ISBN  978-90-272-3250-2.
  4. ^ Mateescu & Salomaa (1997), Příklad 2.1, s. 188
  5. ^ Mateescu & Salomaa (1997), Věta 2.1, str. 187
  6. ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Úvod do teorie automatů, jazyků a výpočtu. Addison-Wesley. ISBN  0-201-02988-X. Cvičení 9.9, s. 230. Ve vydání z roku 2003 byla vypuštěna kapitola o smluvních / kontextově citlivých jazycích.
  7. ^ Sige-Yuki Kuroda (červen 1964). "Třídy jazyků a lineárně ohraničené automaty". Informace a kontrola. 7 (2): 207–223. doi:10.1016 / s0019-9958 (64) 90120-2.
  8. ^ Mateescu & Salomaa (1997), Věta 2.2, str. 190
  • Book, R. V. (1973). "O struktuře kontextově citlivých gramatik". International Journal of Computer & Information Sciences. 2 (2): 129–139. doi:10.1007 / BF00976059. hdl:2060/19710024701.
  • Mateescu, Alexandru; Salomaa, Arto (1997). „Kapitola 4: Aspekty teorie klasického jazyka“. V Rozenberg, Grzegorz; Salomaa, Arto (eds.). Příručka formálních jazyků. Svazek I: Slovo, jazyk, gramatika. Springer-Verlag. 175–252. ISBN  3-540-61486-9.