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

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

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

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

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

где

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

${\displaystyle (P,Q),\quad P\in W(V)V_{N}W(V),\quad Q\in W(V),\quad V=V_{N}\cup V_{T}.}$

Пары называются правилами вывода, и записываются как ${\displaystyle P\to Q}$. Последовательности называются матрицами, и записываются как

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

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

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

${\displaystyle \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 и

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

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

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

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

Пример

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

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

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

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

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

${\displaystyle 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.  (недоступная ссылка с 13-05-2013 [4511 дней] — история)