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

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

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

Матричная грамматика — это упорядоченная четвёрка

$G=(V_{N},V_{T},X_{0},M).$

где

• $V_{N}$ — конечное множество нетерминальных символов
• $V_{T}$ — конечное множество терминальных символов
• $X_{0}\in V_{N}$ — начальный символ
• $M$ — конечное множество непустых последовательностей упорядоченных пар

$(P,Q),\quad P\in W(V)V_{N}W(V),\quad Q\in W(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$-свободной, контектсно-свободной или контекстно-зависимой тогда и только тогда, когда грамматика $G_{1}=(V_{N},V_{T},X_{0},F)$ обладает этим свойством.

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

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

над множеством V и

• $\alpha _{i}=P$ и $\alpha _{r+1}=Q$
• $m\in G$
• $\alpha _{i}=R_{i}P_{i}R^{i}$ и $\alpha _{i+1}=R_{i}Q_{i}R^{i}.$

Если указанные условия выполнены, также говорят, что $P\Rightarrow Q$ выполнено со спецификацией $(m,R_{1})$.

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

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

Пример

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

$G=(\{S,A,B\},\{a,b,c\},S,M)$

где $M$ — совокупность следующих матриц:

$[S\rightarrow XY],\quad [X\rightarrow aXb,Y\rightarrow cY],\quad [X\rightarrow ab,Y\rightarrow c]$

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

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

Этот пример можно найти на страницах 8 и 9 .

Примечания

• ↑  Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1–11. [2]  (недоступная ссылка с 13-05-2013 [3998 дней] — история)