Regulované přepisování - Regulated rewriting

Regulované přepisování je specifická oblast formální jazyky studium gramatických systémů, které jsou schopné převzít určitou kontrolu nad Výroba aplikován v derivačním kroku. Z tohoto důvodu se gramatické systémy studované v teorii regulovaného přepisování nazývají také „Grammars with Controlled Derivations“. Mezi takovými gramatikami lze zaznamenat:

Maticové gramatiky

Základní pojmy

Definice
Maticová gramatika ${displaystyle MG}$, je čtyřnásobnou n-ticí ${displaystyle G = (N, T, M, S)}$ kde
1.- ${displaystyle N}$ je abeceda neterminálních symbolů
2.- ${displaystyle T}$ je abeceda koncových symbolů disjunktních s ${displaystyle N}$
3.- ${displaystyle M = {m_ {1}, m_ {2}, ..., m_ {n}}}$ je konečná sada matic, což jsou neprázdné sekvence ${displaystyle m_ {i} = [p_ {i_ {1}}, ..., p_ {i_ {k (i)}}]}$, s ${displaystyle k (i) geq 1}$, a${displaystyle 1leq ileq n}$, kde každý ${displaystyle p_ {i_ {j}} 1leq jleq k (i)}$, je objednaný pár${displaystyle p_ {i_ {j}} = (L, R)}$bytost${displaystyle Lin (Ncup T) ^ {*} N (Ncup T) ^ {*}, Rin (Ncup T) ^ {*}}$tyto páry se nazývají „produkce“ a označují se${displaystyle Lightarrow R}$. Za těchto podmínek lze matice zapsat jako${displaystyle m_ {i} = [L_ {i_ {1}} ightarrow R_ {i_ {1}}, ..., L_ {i_ {k (i)}} ightarrow R_ {i_ {k (i)}}] }$
4. - S je počáteční symbol

Definice
Nechat ${displaystyle MG = (N, T, M, S)}$ být maticovou gramatikou a nechat ${displaystyle P}$sbírka všech inscenací na matricích ${displaystyle MG}$.Řekli jsme to ${displaystyle MG}$ je typu i podle Chomského hierarchie s ${displaystyle i = 0,1,2,3}$, nebo „zvětšení délky“ nebo „lineární“ nebo „bez“ ${displaystyle lambda}$-productions "právě tehdy, pokud jde o gramatiku ${displaystyle G = (N, T, P, S)}$ má odpovídající vlastnost.

Klasický příklad

Poznámka: převzato z Abrahama 1965, se změnou jmen neterminálů

Kontextově citlivý jazyk ${displaystyle L (G) = {a ^ {n} b ^ {n} c ^ {n}: ngeq 1}}$je generován ${displaystyle CFMG}$${displaystyle G = (N, T, M, S)}$ kde${displaystyle N = {S, A, B, C}}$ je sada terminálů, ${displaystyle T = {a, b, c}}$ je sada terminálů a sada matic je definována jako${displaystyle M:}$${displaystyle left [Sightarrow abcight]}$,${displaystyle left [Sightarrow aAbBcCight]}$,${displaystyle left [Aightarrow aA, Bightarrow bB, Cightarrow cCight]}$,${displaystyle left [Aightarrow a, Bightarrow b, Cightarrow cight]}$.

Časově variační gramatiky

Základní pojmy
Definice
Gramatika časové varianty je pár ${displaystyle (G, v)}$ kde ${displaystyle G = (N, T, P, S)}$ je gramatika a ${displaystyle v: mathbb {N} ightarrow 2 ^ {P}}$ je funkce od množiny přirozených čísel do třídy podmnožin množiny produkcí.

Programované gramatiky

Základní pojmy

Definice

Programovaná gramatika je pár ${displaystyle (G, s)}$ kde ${displaystyle G = (N, T, P, S)}$ je gramatika a ${displaystyle s, f: Pightarrow 2 ^ {P}}$ jsou úspěch a selhat funkce ze sady produkce do třídy podmnožin sady produkce.

Gramatiky s běžným kontrolním jazykem

Základní pojmy

Definice
Gramatika s běžným kontrolním jazykem, ${displaystyle GWRCL}$, je pár ${displaystyle (G, e)}$ kde ${displaystyle G = (N, T, P, S)}$ je gramatika a ${displaystyle e}$ je regulární výraz nad abecedou množiny inscenací.

Naivní příklad

Zvažte CFG${displaystyle G = (N, T, P, S)}$ kde${displaystyle N = {S, A, B, C}}$ je sada terminálů, ${displaystyle T = {a, b, c}}$ je koncová sada a produkční sada je definována jako${displaystyle P = {p_ {0}, p_ {1}, p_ {2}, p_ {3}, p_ {4}, p_ {5}, p_ {6}}}$bytost ${displaystyle p_ {0} = Sightarrow ABC}$${displaystyle p_ {1} = Aightarrow aA}$,${displaystyle p_ {2} = Bightarrow bB}$,${displaystyle p_ {3} = Cightarrow cC}$${displaystyle p_ {4} = Aightarrow a}$,${displaystyle p_ {5} = Bightarrow b}$, a${displaystyle p_ {6} = Cightarrow c}$.Jasně,${displaystyle L (G) = {a ^ {*} b ^ {*} c ^ {*}}}$. Nyní, vzhledem k produkční sadě ${displaystyle P}$ jako abecedu (protože se jedná o konečnou množinu) definujte regulární výraz znovu ${displaystyle P}$:${displaystyle e = p_ {0} (p_ {1} p_ {2} p_ {3}) ^ {*} (p_ {4} p_ {5} p_ {6})}$.

Kombinace gramatiky CFG ${displaystyle G}$ a regulární výraz${displaystyle e}$, získáme CFGWRCL ${displaystyle (G, e) = (G, p_ {0} (p_ {1} p_ {2} p_ {3}) ^ {*} (p_ {4} p_ {5} p_ {6}))}$který generuje jazyk${displaystyle L (G) = {a ^ {n} b ^ {n} c ^ {n}: ngeq 1}}$.

Kromě toho existují další gramatiky s regulovaným přepisováním, čtyři výše uvedené jsou dobrým příkladem toho, jak rozšířit bezkontextové gramatiky s nějakým druhem kontrolního mechanismu k získání a Turingův stroj výkonné gramatické zařízení.

Reference

• Salomaa, Arto (1973) Formální jazyky. Academic Press, řada monografií ACM

• Rozenberg, G .; Salomaa, A. (eds.) 1997, Příručka formálních jazyků. Berlín; New York: Springer ISBN  3-540-61486-9 (sada) (3540604200: v. 1; 3540606483: v. 2; 3540606491: v. 3)

• Dassow, Jürgen; Paun, G. 1990, Regulované přepisování v teorii formálního jazyka ISBN  0387514147. Springer-Verlag New York, Inc. Secaucus, New Jersey, USA, stránky: 308. Střední: vázaná kniha.

• Dassow, Jürgen, Gramatiky s regulovaným přepisováním. Přednáška v 5. doktorském programu „Formální jazyky a aplikace“, Tarragona, Španělsko, 2006.

• Abraham, S. 1965. Některé otázky teorie jazyků, Sborník mezinárodní konference o počítačové lingvistice z roku 1965, s. 1–11, Bonn, Německo,