Регулируемая перезапись - 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}=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}$, и${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, Бонн, Германия,