Матричная грамматика

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

Матричная грамматика — это расширение контекстно-свободной грамматики и один из примеров контролируемой грамматики .

Формальное определение

Матричная грамматика представляет собой упорядоченную четверку $G=(V_{N},V_{T},X_{0},M)$где

• $V_{N}$ представляет собой конечное множество нетерминалов
• $V_{T}$ представляет собой конечный набор терминалов
• $X_{0}$ является особым элементом $V_{N}$, а именно. стартовый символ
• $M$ — конечное множество непустых последовательностей, элементами которых являются упорядоченные пары $(P,Q)$ где

$\quad P\in V^{*}V_{N}V^{*},\quad Q\in V^{*},\quad V=V_{N}\cup V_{T}.$

Пары называются продукцией и записываются как $P\to Q$. Последовательности называются матрицами и могут быть записаны как

$m=[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}].$

Позволять $F$ быть набором всех продукций, фигурирующих в матрицах $m$ матричной грамматики $G$. Тогда матричная грамматика $G$ имеет тип- $i,i=0,1,2,3$, возрастающая по длине , линейная , $\lambda$-free , контекстно-свободный или контекстно-зависимый тогда и только тогда, когда грамматика $G_{1}=(V_{N},V_{T},X_{0},F)$ имеет следующее свойство.

Для матричной грамматики $G$, бинарное отношение $\Rightarrow _{G}$ определяется; также представлен как $\Rightarrow$. Для любого $P,Q\in V^{*}$, $P\Rightarrow Q$ выполняется тогда и только тогда, когда существует целое число $r\geq 1$ такое, что слова

$\alpha _{1},,\ldots ,\alpha _{r+1},\quad P_{1},\ldots ,P_{r},\quad Q_{1},\ldots ,Q_{r},\quad R_{1},\ldots ,R_{r},\quad ,R^{1},\ldots ,R^{r}$

над V существуют и

• $\alpha _{1}=P$ и $\alpha _{r+1}=Q$
• $[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}]$ является одной из матриц $G$
• $\alpha _{i}=R_{i}P_{i}R^{i}$ и $\alpha _{i+1}=R_{i}Q_{i}R^{i}$ для всех $i$ такой, что $1\leq i\leq r.$

Позволять $\Rightarrow ^{*}$ — рефлексивное транзитивное замыкание отношения $\Rightarrow$. Тогда язык, порожденный матричной грамматикой $G$ дается

$L(G)=\{P\in {V_{T}}^{*}|X_{0}\Rightarrow ^{*}P\}.$

Примеры

Рассмотрим матричную грамматику

$G=(\{S,X,Y\},\{a,b,c\},S,M)$

где $M$ представляет собой коллекцию, содержащую следующие матрицы:

$m_{0}:[S\rightarrow XY],\quad m_{1}:[X\rightarrow aXb,Y\rightarrow cY],\quad m_{2}:[X\rightarrow ab,Y\rightarrow c]$

Эти матрицы, содержащие только контекстно-свободные правила, генерируют контекстно-зависимый язык.

$L=\{a^{n}b^{n}c^{n}|n\geq 1\}.$Ассоциативное слово $a^{n}b^{n}c^{n}$является $Aw(a^{n}b^{n}c^{n})=m_{0}m_{1}^{n-2}m_{2},\forall n\geq 2$ и $Aw(abc)=m_{0}m_{2}$.

Этот пример можно найти на страницах 8 и 9 книги. ^[1] в следующей форме:Рассмотрим матричную грамматику

$G=(\{S,X,Y,Z\},\{a,b,c\},S,M)$

где $M$ представляет собой коллекцию, содержащую следующие матрицы:

$m_{0}:[S\rightarrow abc],\quad m_{1}:[S\rightarrow aXbYcZ],\quad m_{2}:[X\rightarrow aX,Y\rightarrow bY,Z\rightarrow cZ],\quad m_{3}:[X\rightarrow ab,Y\rightarrow b,Z\rightarrow c]$

Эти матрицы, содержащие только контекстно-регулярные правила, генерируют контекстно-зависимый язык.

$L=\{a^{n}b^{n}c^{n}|n\geq 1\}.$

Ассоциативное слово $a^{n}b^{n}c^{n}$является $Aw(a^{n}b^{n}c^{n})=m_{1}m_{2}^{n-2}m_{3},\forall n\geq 2$ и $Aw(abc)=m_{0}$.

Характеристики

Позволять ${\ce {MAT^{\lambda }}}$ — класс языков, созданных с помощью матричных грамматик, а MAT — класс языков, созданных с помощью матричных грамматик. $\lambda$-свободные матричные грамматики.

• Тривиально, MAT включен в ${\ce {MAT^{\lambda }}}$.
• Все контекстно-свободные языки находятся в MAT , а все языки в ${\ce {MAT^{\lambda }}}$ являются рекурсивно перечислимыми .
• MAT замкнут при объединении , конкатенации , пересечении с обычными языками и перестановке.
• Все языки в MAT могут быть созданы с помощью контекстно-зависимой грамматики .
• Существует контекстно-зависимый язык, не принадлежащий ${\ce {MAT^{\lambda }}}$ ^[2] .
• Каждый язык, созданный с помощью матричной грамматики только с одним терминальным символом, является регулярным.

Открытые проблемы

Неизвестно, существуют ли языки на ${\ce {MAT^{\lambda }}}$ которых нет в МАТ , и неизвестно, есть ли ${\ce {MAT^{\lambda }}}$ содержит языки, которые не являются контекстно-зависимыми ^[3] .

Сноски

• ^ Абрахам, С. Некоторые вопросы теории языка. Международная конференция по компьютерной лингвистике, 1965. стр. 1–11. [4]
• ^ Георге Паун, Мембранные вычисления: Введение, Springer-Verlag New York, Inc., Секаукус, Нью-Джерси, США, 2002. стр. 30–32.