Меню Главная Случайная статья Настройки Матричная грамматика Материал из https://ru.wikipedia.org Матричная грамматика — это формальная грамматика, в которой правила вывода группируются в конечные последовательности. Правила вывода не могут применяться по отдельности, а только в последовательности. При применении такой последовательности, замена производится в соответствии с каждым правилом в последовательности, с первой по последнюю. Последовательности называют матрицами. Матричная грамматика является расширением контекстно-свободной грамматики. Формальное определение Матричная грамматика — это упорядоченная четвёрка ${\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 [1]. Примечания   brahm, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1–11. [2]  (недоступная ссылка с 13-05-2013 [4509 дней] — история)