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

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

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

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

$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$-свободной, контектсно-свободной or контекстно-зависимой если и только если грамматика $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,, \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^nb^nc^n|n \ge 1\}.$

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

Примечания

• ↑  Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1–11. [1]