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

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

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

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

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 ^[1].

Примечания править

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

[1]