About phrase-structure grammar property.pdf В теории формальных грамматик словарь языка X = {x1 , . . . , x n } обычно на-зывают терминальным множеством, тогда как нетерминальным называют конечноемножество Z = {z1 , . . . , zm} вспомогательных символов, необходимых для заданияграмматических правил (грамматики) данного языка. Для элементов этих множествопределены операции конкатенации и формальной суммы, приводящие к мономам имногочленам [1].Если мономы и многочлены построены в соответствии с грамматическими пра-вилами данного языка, то они интерпретируются как предложения и совокупностипредложений. Рассмотрение совокупности всех грамматически правильных предложе-ний приводит к необходимости изучать формальные степенные ряды от терминальныхсимволов.Грамматики непосредственно составляющих (нс-грамматики) являются важнымподклассом контекстно-зависимых грамматик (кз-грамматик); в то же время контекст-но-свободные грамматики (кс-грамматики) являются частным случаем нс-грамматик.Нс-грамматике сопоставима система символьных уравненийа к z , = pk ( x , z ) , j = 1,...,m, kj = 1 , . . . , L , . (1)Ее решением является совокупность (а1 z ^ x ^ i , . . . , а^"z^™ (ж)втГ) формальных сте-пенных рядов от терминальных переменных ж = (ж1,... , xn), а ряды ак z^ (x)ekj явля-ются нс-языком, определяемым данной грамматикой. Мономы ак и ekj называютсяконтекстом. Рассмотрим вполне определенные нс-грамматики, которые сопоставимысистемам уравнений видао,-zjej = p,(ж, z ), j = 1 . . . , m. (1/)Эффективным инструментом изучения решений таких систем уравнений являетсякоммутативный образ этой системы - новая система уравнений, переменные в ко-торой рассматриваются как коммутативные, например из поля комплексных чисел.Понятно, что формальные степенные ряды (z1(x),... , zm(x)), являющиеся решениямиисходной системы (1/), переходят в степенные ряды, представляющие алгебраическиефункции. Коммутативный образ некоторого многочлена или ряда r будем обозначатькак ci(r) (commutative image) [2].Произведем ряд замен вида zj = а, z, в,. Получим систему уравненийzj = P j ( x , z ) j = 1 , . . . , m . (2)Запишем систему уравнений (2) в видеqj (x, z,z') = 0, j = 1,...,m. (3)Решением этой системы назовем выражение символов zj в виде формальных степен-ных рядов от x, подстановка которых в многочлены qi(x,z,z/) обращает их в нуль.Определим условия, при которых система (2) имеет такое решение.Теорема 1. Если выполняется неравенството исходная система имеет решение в виде формальных степенных рядов.Легко показать, что элементы главной диагонали матрицы Якоби содержат сум-му мономов терминального алфавита (обусловленную линейной зависимостью неко-торых zj от соответствующих zj) и некоторого скаляра. Таким образом, в силу невы-рожденности матрицы Якоби в начале координат можно сделать линейную заменупеременных zj, в результате которой эта матрица становится единичной, что, учиты-вая ряд проведенных замен, приводит систему (3) к видув результате чего её можно решать методом последовательных приближений. Искомыеряды равны линейной комбинации получаемых рядов.Ранее подобное свойство было доказано для контекстно-свободных грамматик [3].

Скачать электронную версию публикации