Регулируемый рерайтинг

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

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

Основные понятия

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

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

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

Примечание: взято из Авраама 1965 г., с изменением названий нетерминалов.

Контекстно-зависимый язык $L(G)=\{a^{n}b^{n}c^{n}:n\geq 1\}$генерируется $CFMG$$G=(N,T,M,S)$ где $N=\{S,A,B,C\}$ это нетерминальный набор, $T=\{a,b,c\}$ это набор терминалов,а набор матриц определяется как $M:$$\left[S\rightarrow abc\right]$, $\left[S\rightarrow aAbBcC\right]$, $\left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right]$, $\left[A\rightarrow a,B\rightarrow b,C\rightarrow c\right]$.

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

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

Программированные грамматики

Основные понятия

Определение

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

Грамматики с обычным управляющим языком

Основные понятия

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

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

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

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

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

Ссылки

• Саломаа, Арто (1973) Формальные языки . Academic Press, серия монографий ACM
• Розенберг, Г.; Саломаа А. (ред.) 1997, Справочник по формальным языкам . Берлин; Нью-Йорк: Спрингер ISBN  3-540-61486-9 (set) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491: v. 3)
• Дассов, Юрген; Паун, Г. 1990, Регулируемое переписывание в теории формального языка. ISBN   0387514147 . Springer-Verlag New York, Inc. Секаукус, Нью-Джерси , США, Страниц: 308. Материал: Твердый переплет.
• Дассов, Юрген, Грамматики с регулируемым переписыванием . Лекция в рамках 5-й докторской программы «Формальные языки и приложения», Таррагона, Испания, 2006 г.
• Абрахам, С. 1965. Некоторые вопросы теории языка , Труды Международной конференции 1965 года по компьютерной лингвистике , стр. 1–11, Бонн, Германия,