On representation of contextfree languages by diagonals of linear laguages.pdf В теории контекстно-свободных языков (кс-языков) и грамматик словарь языкаX = { x i , . . . , x n} обычно называют терминальным множеством, тогда как нетерминальнымназывают конечное множество Z = {z1, ... , zm} вспомогательных символов,необходимых для задания грамматических правил (грамматики) данного языка. Дляэлементов этих множеств определены операции конкатенации и формальной суммы,приводящие к мономам и многочленам.Если последние построены в соответствии с грамматическими правилами данногокс-языка, то эти мономы и многочлены интерпретируются как его предложения исовокупности предложений. Рассмотрение совокупности всех грамматически правильных предложений кс-языка приводит к необходимости изучать формальные степенныеряды от терминальных символов.Кс-грамматике сопоставляется система символьных уравненийzj = Vj(x,z),j ^ . . ^ m (1)называемая системой уравнений Хомского - Щютценберже. Ее решением являетсясовокупность (z1(x),... , zm(x)) формальных степенных рядов от терминальных переменныхx = (x1, . . . , x n), а ряд z1 (x) и является кс-языком, определяемым даннойграмматикой [1].Эффективным инструментом изучения решений систем уравнений Хомского -Щютценберже является коммутативный образ этой системы - новая система уравнений,переменные в которой рассматриваются уже как коммутативные, например,из поля комплексных чисел [2]. Понятно, что и формальные степенные ряды(z1(x),... , zm(x)), являющиеся решениями исходной системы (1), переходят в степенныеряды, представляющие алгебраические функции. Осталось заметить, что коммутативныйобраз некоторого многочлена или ряда r удобно обозначать как ci(r)(commutative image).Хорошо изучен подкласс линейных кс-языков, для которых уравнения системы (1)линейны по переменным Zj, j = 1,.. .,m. А именно, достаточно изучена структураформальных степенных рядов, представляющих такие языки. Оказалось [2], что существуюттак называемые аффинные кс-языки над терминальным множеством X ,коммутативные образы которых являются диагоналями коммутативных образов линейныхязыков над терминальным множеством {x 0} U X , содержащем один дополнительныйсимвол. В диагональ «выбираются» те мономы, у которых степень по x 1равна степени по x0.Запишем систему уравнений (1) в видеqj(x,z) = 0,j ^ . . ^ m (2)возьмем ее подсистему qj(x, z) = 0, j = 2,... , m, и рассмотрим систему уравненийq*(x,z) = ° , j = 2,. . . ,m, (3)составленную из старших взвешенно-однородных по переменным z2, . . . , zm с весом(w2,. .. , wm) составляющих многочленов qj (x, z). Тогда имеет место теорема 1.Теорема 1. Пусть подсистема уравнений (3) не зависит от x и z1 и имеет единственныйкорень z2 = ... = zm = 0. Тогда существует линейный язык над терминальныммножеством {x 0} U X , такой, что коммутативный образ кс-языка, определяемогосистемой (2), является диагональю его коммутативного образа.Ранее подобное утверждение было доказано только для случая однородных частеймногочленов qj(x,z).

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