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

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

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

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

$G=(V_N,V_T,X_0,M).$

где

• $V_N$ — конечное множество нетерминальных символов
• $V_T$ — конечное множество терминальных символов
• $X_0\in V_N$ — начальный символ
• $M$ — конечное множество непустых последовательностей упорядоченных пар

$(P,Q),P\in W(V)V_{N}W(V),Q\in W(V),V=V_N\cup V_T.$

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

$m=[P_1\to Q_1,\dots ,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\ge 1$ такое, что существуют слова

${\alpha }_1,,\dots ,{\alpha }_{r+1},P_1,\dots ,P_r,R_1,\dots ,R_r,,R^1,\dots ,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 }^{\ast }$ — рефлексивное транзитивное замыкание отношения $\Rightarrow$. Тогда, язык, порождаемый матричной грамматикой $G$ опредеяется следующим образом:

$L(G)=\{P\in W(V_T)|X_0{\Rightarrow }^{\ast }P\}.$

Пример

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

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

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

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

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

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

Этот пример можно найти на страницах 8 и 9 Шаблон:Ref.

Примечания

• Шаблон:Note Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1–11. [1] Шаблон:Недоступная ссылка