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

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

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

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

<math>G = (V_N, V_T, X_0, M).</math>

где

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

<math>(P, Q), \quad P \in W(V) V_N W(V), \quad Q \in W(V), \quad V = V_N \cup V_T.</math>

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

<math>m = [P_1 \to Q_1, \ldots, P_r \to Q_r].</math>

Пусть <math>F</math> -- множество всех правил вывода в матрицах <math>m</math> матричной грамматики <math>G</math>. Тогда грамматика <math>G</math> является грамматикой типа <math>i, i = 0, 1, 2, 3</math>, неукорачивающей, линейной, <math>\lambda</math>-свободной, контектсно-свободной or контекстно-зависимой если и только если грамматика <math>G_1 = (V_N, V_T, X_0, F)</math> обладает этим свойством.

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

<math>\alpha_1,, \ldots, \alpha_{r + 1}, \quad P_1, \ldots, P_r, \quad R_1, \ldots, R_r, \quad, R^1, \ldots, R^r</math>

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

• <math>\alpha_i = P</math> и <math>\alpha_{r + 1} = Q</math>
• <math>m \in G</math>
• <math>\alpha_i = R_i P_i R^i</math> и <math>\alpha_{i + 1} = R_i Q_i R^i.</math>

Если указанные условия выполнены, также говорят, что <math>P \Rightarrow Q</math> выполнено со спецификацией <math>(m, R_1)</math>.

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

<math>L(G) = \{P \in W(V_T) | X_0 \Rightarrow^{*} P\}.</math>

Пример

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

<math>G = (\{S, A, B\}, \{a, b, c\}, S, M)</math>

где <math>M</math> -- совокупность следующих матриц:

<math>[S \rightarrow XY], \quad [X \rightarrow aXb, Y \rightarrow cY], \quad [X \rightarrow ab, Y \rightarrow c]</math>

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

<math>L = \{a^nb^nc^n|n \ge 1\}.</math>

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

References

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