Введение

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

Свойства

Пусть MAT^\lambda будет классом языков, порождаемых матричными грамматиками, а MAT — классом языков, порождаемых свободными матричными грамматиками. Очевидно, MAT включается в MAT^\lambda. Все контекстно-свободные языки находятся в MAT, и все языки в MAT^\lambda рекурсивно перечислимы. MAT замкнут относительно объединения, конкатенации, пересечения с регулярными языками и перестановки. Любой язык в MAT может быть порожден контекстно-зависимой грамматикой. Существует контекстно-зависимый язык, который не принадлежит MAT^\lambda. Каждый язык, порождаемый матричной грамматикой, содержащей только один терминальный символ, является регулярным.

Открытые проблемы

Неизвестно, существуют ли языки в MAT^\lambda, которых нет в MAT, и также неизвестно, содержит ли MAT^\lambda языки, не являющиеся контекстно-зависимыми.

Сноски

Ábrahám, S. Некоторые вопросы теории языка. Международная конференция по вычислительной лингвистике, 1965. с. 1–11. Георге Паун, Membrane Computing: An Introduction, Springer Verlag New York, Inc., Secaucus, NJ, США, 2002. с. 30–32.