Регулируемая перезапись - Regulated rewriting

Регулируемая перезапись это особая область формальные языки изучение грамматических систем, способных каким-то образом контролировать производство применяется на этапе деривации. По этой причине грамматические системы, изучаемые в теории регулируемого перезаписывания, также называются «грамматиками с контролируемыми производными». Среди таких грамматик можно отметить:

Матричные грамматики

Базовые концепты

Определение
Матричная грамматика, ${displaystyle MG}$, является четырехкортежным ${displaystyle G = (N, T, M, S)}$ куда
1.- ${displaystyle N}$ это алфавит нетерминальных символов
2.- ${displaystyle T}$ представляет собой алфавит терминальных символов, не пересекающихся с ${displaystyle N}$
3.- ${displaystyle M = {m_ {1}, m_ {2}, ..., m_ {n}}}$ - конечный набор матриц, которые являются непустыми последовательностями ${displaystyle m_ {i} = [p_ {i_ {1}}, ..., p_ {i_ {k (i)}}]}$, с ${displaystyle k (i) geq 1}$, и${displaystyle 1leq ileq n}$, где каждый ${displaystyle p_ {i_ {j}} 1leq jleq k (i)}$, - упорядоченная пара${displaystyle p_ {i_ {j}} = (L, R)}$существование${displaystyle Lin (Ncup T) ^ {*} N (Ncup T) ^ {*}, Rin (Ncup T) ^ {*}}$эти пары называются "продукциями" и обозначаются${displaystyle Lightarrow R}$. В этих условиях матрицы можно записать как${displaystyle m_ {i} = [L_ {i_ {1}} ightarrow R_ {i_ {1}}, ..., L_ {i_ {k (i)}} ightarrow R_ {i_ {k (i)}}] }$
4.- S - начальный символ

Определение
Позволять ${displaystyle MG = (N, T, M, S)}$ - матричная грамматика и пусть ${displaystyle P}$совокупность всех производств по матрицам ${displaystyle MG}$.Мы сказали, что ${displaystyle MG}$ имеет тип i согласно иерархии Хомского с ${displaystyle i = 0,1,2,3}$, или «увеличивающаяся длина», или «линейный», или «без ${displaystyle lambda}$-продукции "тогда и только тогда, когда грамматика ${displaystyle G = (N, T, P, S)}$ обладает соответствующим свойством.

Классический пример

Примечание: взято из Abraham 1965, с изменением нетерминальных имен.

Контекстно-зависимый язык ${displaystyle L (G) = {a ^ {n} b ^ {n} c ^ {n}: ngeq 1}}$генерируется ${displaystyle CFMG}$${displaystyle G = (N, T, M, S)}$ куда${displaystyle N = {S, A, B, C}}$ - нетерминальное множество, ${displaystyle T = {a, b, c}}$ - терминальный набор, а набор матриц определяется как${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]}$.

Грамматики временного варианта

Базовые концепты
Определение
Грамматика временного варианта - это пара ${displaystyle (G, v)}$ куда ${displaystyle G = (N, T, P, S)}$ это грамматика и ${displaystyle v: mathbb {N} ightarrow 2 ^ {P}}$ - функция от множества натуральных чисел до класса подмножеств множества продукций.

Программируемые грамматики

Базовые концепты

Определение

Программируемая грамматика - это пара ${displaystyle (G, s)}$ куда ${displaystyle G = (N, T, P, S)}$ это грамматика и ${displaystyle s, f: Pightarrow 2 ^ {P}}$ являются успех и провал функций от множества производств к классу подмножеств множества производств.

Грамматики с обычным контрольным языком

Базовые концепты

Определение
Грамматика с обычным контрольным языком, ${displaystyle GWRCL}$, пара ${displaystyle (G, e)}$ куда ${displaystyle G = (N, T, P, S)}$ это грамматика и ${displaystyle e}$ является регулярным выражением по алфавиту множества производств.

Наивный пример

Рассмотрим CFG${displaystyle G = (N, T, P, S)}$ куда${displaystyle N = {S, A, B, C}}$ - нетерминальное множество, ${displaystyle T = {a, b, c}}$ - конечный набор, а производственный набор определяется как${displaystyle P = {p_ {0}, p_ {1}, p_ {2}, p_ {3}, p_ {4}, p_ {5}, p_ {6}}}$существование ${displaystyle p_ {0} = стрелка ABC}$${displaystyle p_ {1} = стрелка aA}$,${displaystyle p_ {2} = Bightarrow bB}$,${displaystyle p_ {3} = Cightarrow cC}$${displaystyle p_ {4} = стрелка a}$,${displaystyle p_ {5} = Bightarrow b}$, и${displaystyle p_ {6} = Cightarrow c}$.Четко,${displaystyle L (G) = {a ^ {*} b ^ {*} c ^ {*}}}$. Теперь, учитывая набор производств ${displaystyle P}$ как алфавит (поскольку это конечный набор), определите регулярное выражение над ${displaystyle P}$:${displaystyle e = p_ {0} (p_ {1} p_ {2} p_ {3}) ^ {*} (p_ {4} p_ {5} p_ {6})}$.

Объединение грамматики CFG ${displaystyle G}$ и регулярное выражение${displaystyle e}$, получаем CFGWRCL ${displaystyle (G, e) = (G, p_ {0} (p_ {1} p_ {2} p_ {3}) ^ {*} (p_ {4} p_ {5} p_ {6}))}$который порождает язык${displaystyle L (G) = {a ^ {n} b ^ {n} c ^ {n}: ngeq 1}}$.

Помимо других грамматик с регулируемой перезаписью, четыре приведенные выше являются хорошими примерами того, как расширить контекстно-свободные грамматики с каким-то механизмом управления для получения Машина Тьюринга мощный грамматический аппарат.

Рекомендации

• Саломаа, Арто (1973) Формальные языки. Academic Press, серия монографий ACM

• Розенберг, Г .; Саломаа А. (ред.) 1997 г., Справочник формальных языков. Берлин; Нью-Йорк: Спрингер ISBN  3-540-61486-9 (набор) (3540604200: v. 1; 3540606483: v. 2; 3540606491: v. 3)

• Дассов, Юрген; Паун, Г. 1990, Регулируемый перезапись в теории формального языка ISBN  0387514147. Springer-Verlag New York, Inc. Secaucus, Нью-Джерси, США, Страниц: 308. Материал: Твердый переплет.

• Дассов, Юрген, Грамматики с регулируемой перезаписью. Лекция 5-й программы PhD "Формальные языки и приложения", Таррагона, Испания, 2006 г.

• Авраам, С. 1965. Некоторые вопросы теории языка, Материалы Международной конференции по компьютерной лингвистике 1965 г., стр. 1–11, Бонн, Германия,