автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Распознавание и синтаксический анализ контекстно-свободных языков программирования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

УДК 519.682 На правах рукописи

САФОНОВ КОНСТАНТИН ВЛАДИМИРОВИЧ

РАСПОЗНАВАНИЕ И СИНТАКСИЧЕСКИЙ АНАЛИЗ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Красноярск — 2006

Работа выполнена в Красноярском государственном техническом университете.

Научный консультант: доктор физико-математических наук,

профессор Носков Михаил Валерианович

Официальные оппоненты:

член-корреспондент РАН,

профессор Федотов Анатолий Михайлович

доктор физико-математических наук, профессор Кытманов Александр Мечиславович

доктор физико-математических наук, профессор Семенов Алексей Львович

Ведущая организация: Институт программных систем РАН

(г. Переславль-Залесский)

Защита состоится 16 марта 2006 г. в 1400 часов на заседании диссертационного совета Д 212.098.03 в Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Акад. Киренского, 26, ауд. Г 4-17, тел. (8-3912) 91-21-94, факс (8-3912) 43-06-92.

С диссертацией можно ознакомиться в библиотеке Красноярского государственного технического университета.

Отзывы в 2-х экземплярах, заверенные печатью, просим высылать по указанному адресу.

Автореферат разослан « // » февраля 2006 г.

Ученый секретарь

диссертационного совета

кандидат технических наук, профессор КГТУ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. Фундаментальным свойством большинства языков программирования является принадлежность классу контекстно-свободных языков (кс-языков), которые были введены в 50-х годах прошлого века выдающимся американским лингвистом Н. Хомским. Действительно, описание языка программирования определяет действующие в нем правила подстановки (продукции), совокупность которых является контекстно-свободной грамматикой (кс-грамматикой) и порождает соответствующий кс-язык, В связи с этим среди формальных языков Хомского именно кс-языки играют наиболее важную роль в теоретическом программировании. Основные аспекты проблематики, связанной с исследованием различных языков программирования, например, проблема определенности (однозначности) языка, его синтаксического и семантического анализа и др., могут быть рассмотрены с общей точки зрения, а именно, применительно к кс-языкам.

Пусть Х = {*,,..., — конечное множество терминальных символов (слов) языка, например, операторов языка программирования, букв, цифр и т.д., а У = {уи.-,}>„} - множество нетерминальных символов, необходимых для задания грамматики языка, у, — символ (аксиома), означающий начало предложения (программы). На множестве X и У введены операции конкатенации и формальной суммы, а также умножения на элементы числового поля. Тогда грамматике сопоставляется система полиномиальных символьных уравнений Хомского-Щютценберже

У1=РЛх,у), ¡ = 1,...,т, (1)

называемая собственной системой, коэффициенты которой удовлетворяют определенным условиям. Первая компонента у, решения (у((х).....%■(*)) этой системы, полученного методом последовательных приближений в виде формальных степенных рядов от ДГ1,..., хт является данным кс-языком, т.е. формальной суммой мономов — всех предложений (программ) данного языка. Важнейший подкласс кс-языков образуют наиболее простые из них - линейные, в частно-

сти, регулярные языки, для которых все многочлены системы (1) линейны по уп У = т.

Ранее в исследовании кс-языков основную роль играли методы алгебры и дискретной математики, например, анализ деревьев вывода мономов. При этом изучение символьной системы (1), которая содержит полную информацию о кс-языке, не проводилось. Прежде всего, это было связано с недостаточно разработанными методами многомерного комплексного анализа, позволяющими исследовать решения таких систем. Несмотря на значительные результаты, применение методов дискретной математики не позволило решить целый ряд важных проблем, например, проблему В.М. Глушкова распознавания кс-языков Хомского, т.е. установления их «внутренних» характеристических свойств, отличающих кс-языки от произвольных формальных языков над фиксированным множеством терминальных символов, проблему беступикового синтаксического анализа таких языков, проблему изучения кс-языков Хомского по свойствам системы уравнений Хомского-Щютценберже (1) и многие другие. В настоящей диссертации на основе полученных новых результатов в области комплексного анализа получены новые методы распознавания кс-языков и изучения их свойств, что имеет значительную актуальность в теории программирования.

Цель работы. Получение новых методов распознавания кс-языков (в том числе, языков программирования) и изучения их свойств на основе исследования определяющей системы (1).

Методика исследования. В диссертации использованы методы алгебры, комплексного анализа и теории формальных грамматик.

Научная новизна. Основные результаты диссертации состоят в следую-

хцем:

1. Решена проблема В.М. Глушкова распознавания кс-языков Хомского (в том числе, языков программирования), указаны соответствующие вычислительные алгоритмы.

2. Получен ряд новых необходимых, а также достаточных условий принадлежности формального языка классу кс-языков.

3. Разработан алгоритм беступикового синтаксического анализа кс-языков (языков программирования), основанный на предложенном автором методе «мономиальных меток».

4. Решена проблема установления алгебраичности суммы степенного ряда - доказан критерий алгебраичности, обобщающий известный критерий Кроне-кера о рациональности (1881 г.); полученный результат используется в диссертации при исследовании кс-языков.

5. В соответствии со свойствами системы (1) введен широкий класс нелинейных аффинных кс-языков, для которых доказано, что они образуются из линейных языков над более широким терминальным множеством в результате простой «процедуры диагонализации»; тем самым частично решена проблема определения свойств кс-языка по системе уравнений Хомского-Щготценберже.

Все основные результаты диссертации являются новыми и получены лично автором.

Теоретическая значимость. Полученные в диссертации результаты существенно развивают теорию кс-языков программирования. Они доказаны новыми для этой теории методами, которые могут быть полезными и в дальнейших исследованиях.

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

Апробация работы. Результаты диссертации докладывались в Красноярском государственном техническом университете, Красноярском, Новосибирском, Томском государственных университетах, Институте математики им. С.Л. Соболева СО РАН, Институте динамики систем и теории управления СО РАН,

на всесоюзных, всероссийских и международных конференциях по комплексному анализу и его приложениям (1982—2003 гг.),

на Сибирских конгрессах по индустриальной и прикладной математике (1998 г., 2000 г.),

на международных и всероссийских конференциях по математическим моделям и методам их исследования (1997-2003 гг.),

на Сибирских научных школах-семинарах с международным участием по проблемам компьютерной безопасности и криптографии (2003, 2005 гг.),

на всероссийской конференций с международным участием «Математика, ее приложения и математическое образование» (2005 г.),

на всероссийской конференции «Математика, информатика, управление» (2005 г.) и др.

Публикации. По теме диссертации опубликовано более 30 работ, наиболее значительные из которых приведены ниже, из них 10 работ опубликованы в журналах, которые включены ВАК в Перечень ведущих научных рецензируемых журналов и изданий, а также в иностранных научных рецензируемых журналах. Основные результаты диссертации опубликованы в изданиях, входящих в указанный Перечень. Из работы [2], выполненной в соавторстве, в диссертацию включены результаты, принадлежащие лично автору.

Структура диссертации. Диссертационная работа состоит из введения, вспомогательной главы, пяти глав и списка литературы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении, состоящем из двух разделов, дан обзор результатов по теории кс-языков, полученных С. Гинзбургом, A.B. Гладким, В.М. Глушковым, Ш. Грейбах, Р.Дж. Париком, A.JI. Семеновым, Е. Шамиром, М.П. Щютценбер-же и другими учеными. Кратко сформулированы основные результаты диссертации, формулируются цели исследования, и приводится краткое изложение полученных результатов.

Вспомогательная глава содержит анализ основных направлений математической теории формальных языков программирования.

Глава 1 «Контекстно-свободные языки, их синтаксический анализ и коммутативные образы» состоит из четырех разделов. В разделе 1.1 «Кс-грамматики и порождаемые ими языки» приводятся необходимые сведения, рассматриваются примеры структурного анализа мономов (предложений). В разделе 1.2 «Идентификаторы языков программирования и их задание кс-грамматиками» рассматривается различные формы задания соответствующих грамматик.

Раздел 1.3 «Проблема синтаксического анализа кс-языков программирования» посвящен алгоритмам беступикового синтаксического анализа кс-языка. Рассматривается кс-язык, порожденный грамматикой (совокупностью продукций):

У/ ~+/п(х>У)>->У: -»/;?,(*».>'), I =1,...,т,

где /ц(х,у) - мономы от некоммутативных символьных переменных из множества X и У (левые части продукций содержат единственный символ и применяется независимо от контекста); у,— выделенный символ, означающий начало предложения (программы). Грамматике ставится в соответствие система символьных уравнений (1), где

Р,(х,у) = /п (х,у) + ...+ Д (х,у)

(грамматика в форме Хомского-Щютценберже), решение этой системы методом последовательных приближений:

уГ1) = Р^Ук)), У0) =(о.....0), /о = *=о.и,

дает, в частности, выражение переменной у] (кс-языка) в виде формального степенного ряда

У, =И<У1>™1 >щ . (2)

где ч!— мономы от дг],____ хп , которые являются всевозможными правильными

предложениями (программами) этого языка.

Поставим в соответствие системе (1) «расширенную» систему символьных уравнений

У,- = Р(х,У,0 '■= 1я/ц{Х>У) + — + (Х>У)> ' = т, (3)

где (у — дополнительные символьные переменные (множители) при мономах -«мономиальиые метки». При решении этой системы методом последовательных приближений у(0) =(0,...,0), £ = 0.1,..., первая компонента решения, выраженная формальным степенным рядом от х = ( = совпадает при ^ = е, где е - пустая цепочка, с рядом (2).

Итерации метода последовательных приближений дают мономы возрастающей длины, и через конечное число шагов их степень (число символов лг,,...,хя) превысит степень заданного монома IV (заданное число символов программы). «Считывая» мономы необходимой степени и пропуская при этом метки / , можно определить, есть ли среди них моном Каждая переменная

содержащаяся в соответствующем мономе, указывает, что при его выводе использована продукция у, —» /у(х,у). Таким образом, можно определить, какие

продукции и сколько раз использованы при выводе монома и' (написании программы) с точностью до порядка их применения, а именно это и требуется при решении проблемы синтаксического анализа.

Таким образом, в разделе 1.3 доказана следующая

ТЕОРЕМА 1.1. Метод мономиалъных меток, заключающийся в решении системы (3) методом последовательных приближений, позволяет провести за конечное число шагов беступиковый (безостановочный) синтаксический анализ любой заданной программы ж.

Пример. Проведем данным методом синтаксический анализ фрагмента арифметической программы (((а + Ъ)*Ъ*Ь) на языке программирования, который порожден грамматикой, содержащей систему продукций:

У, (У, * Уг X У, -> (« + Ь), у2 -> Ъ.

Здесь +, *, (,), а, Ъ — терминальные символы, обозначим их символами х|,л;2,хз,*4)х5,х6 соответственно, тогда программа и» примет вид:

Решая систему (3) у, = 1„хъу[хгг1х< + Г,,*,^^*,, _у, = Г21х6, методом последовательных приближений, получаем итерацию решения:

У = ^^nxг^^\xi^nxгxix\xtxixг^г\xtx'x1^nxix^ 'и^з^з*!^*«» 'аЛ)-

Первый моном совпадает с искомой программой при = /12 = /2] —е (пустая цепочка), а число вхождений переменных показывает, сколько раз использованы соответствующие продукции грамматики: продукция у, —> (у, * ) использована дважды, продукция ух —> {а + Ь) - один раз и продукция уг->Ь -два раза.

Теорема 1.1 дает принципиальное решение задачи беступикового синтаксического анализа любого кс-языка. Алгоритм может быть полезен при разработке новых языков программирования: для любой наперед заданной длины программы Ы, принципиально возможно установить, будут ли однозначными все программы, длина которых не превосходит N. Это тем более важно, что доказательство определенности (однозначности) кс-языка, т.е. всей совокупности его правильных программ является, как известно, алгоритмически неразрешимой проблемой. Метод мономиальных меток позволяет проследить «траекторию» каждого монома при итерациях решения системы Хомского-Щютценберже.

В разделе 1.4 «Коммутативные образы (производящие функции) кс-языков» определяется коммутативный образ формального языка, являющийся важным инструментом его исследования, рассматриваются его свойства. Впервые коммутативный образ языка рассмотрел А.Л. Семенов, применивший его для решения алгоритмических проблем, связанных с кс-грамматиками.

Поставим в соответствие формальному степенному ряду (или многочлену) ряд (многочлен) с комплексными переменными, задав отображение терминальных X} и нетерминальных у] символов из множества в множество комплексных переменных, причем за нетерминальными переменными у, оставляем прежние обозначения, а терминальные символы х^ отображаем в комплексные переменные г^ соответственно, тогда {у,г) е С"*". Таким образом, по-

лучаем фиксированный гомоморфизм, который ставит в соответствие формальному ряду (многочлену)

Г - £< .

I

его коммутативный образ, т.е. степенной ряд (многочлен) от комплексных переменных

к

где

*Х! (и1,)-^.....#1,(1»¡)-к„

а #с(б?) - число вхождений символа с в моном с1.

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

В случае комплексных переменных у еС" еС" коммутативный образ собственной системы (1) имеет в окрестности нуля (0,0)еСт+л единственное голоморфное решение (у1(г),...,ут(г)), где yJ(z) — алгебраические функции. Действительно, условие того, что система (1) — собственная, состоит в том, что многочлены р, (*,>■) не содержат мономов у] не, где е - пустая цепочка, потому, записывая коммутативный образ системы в виде

чЛг,у) = У1~р1(2,у) = 0,1=1.....т, (4)

видим, что эти условия равносильны условию теоремы о неявном отображении:

9,(0,0) = 0, / = 1.....

где ¿>д - символ Кронекера (метод последовательных приближений дает в этом случае тейлоровские разложения голоморфных координат единственного решения, и первая из них является коммутативным образом соответствующего кс-языка).

С другой стороны, коммутативный образ системы символьных уравнений (1) является аналогом ее характеристической системы. Как известно, характеристические уравнения играют фундаментальную роль при решении различного рода систем уравнений в виде дискретных или непрерывных числовых функций, однако применительно к символьным уравнениям роль корней соответствующих характеристических систем уравнений не была достаточно изучена. Как оказалось, характеристические уравнения (в нашем случае - коммутативные образы грам

матик Хомского-Щютценберже) позволяют установить некоторые фундаментальные свойства символьных решений (кс-языков), например, свойство такого решения быть «диагональю» языка более простого класса.

Глава 2 «Фундаментальные свойства коммутативных образов контекстно-свободных языков» посвящена изучению структуры степенных рядов коммутативных образов кс-языков. Коммутативный образ кс-языка является голоморфной в окрестности начала координат алгебраической функцией, поскольку удовлетворяет системе полиномиальных уравнений, составленной из коммутативных образов уравнений Хомского-Щютценберже. Согласно алгебраическому варианту фундаментальной теоремы Гартогса, алгебраичность голоморфной в некоторой области функции равносильна ее алгебраичности по каждой переменной при фиксированных значениях остальных переменных. Таким образом, необходимо, прежде всего, найти условия на коэффициенты степенного ряда одного переменного

*>о

которые характеризуют алгебраичность его суммы. Такие условия получены в разделе 2.1 «Решение проблемы установления алгебраичности суммы степенного ряда (коммутативного образа формального языка)».

Вопрос о рациональности суммы степенного ряда (5) решается с помощью хорошо известного критерия Кронекера (1881 г.), согласно которому рациональность равносильна тому, что при j> у0, / > /0, равны нулю определители Ганкеля

а] - а]+1

■■• а]+г I

Актуальный вопрос о существовании подобного критерия, дающего возможность установить алгебраичность суммы степенного ряда, долгое время оставался открытым.

Решение этого вопроса состоит в следующем. Обозначим

=!>.■«*-<> ^¿^ЕЛ ¿=0,1,..., у=2,з..„

1=0 1-0

тогда имеет место

ТЕОРЕМА 2.1 .Для того чтобы функция (5) была алгебраической, необходимо и достаточно существование чисел <3, ]о , 1п , таких, что при всех ] 2: _/0,/ > /0 выполнены равенства Н^1){с1) = 0, где

я)'>(£/) =

— обобщенный определитель Ганкеля степени <1, а число д=(1+ 1)с1-1.

Н/} =

ау+1 а]

О)

а.

j+l+1

(1)

(1)

I

(1)

1

V-1)

(<М)

1

(1)

(1)

(¿-о

Теорема 2.1 обобщает критерий Кронекера о рациональности: если функция — рациональная, то степень определяющего ее многочлена с1 = 1, и имеет место равенство нулю классического определителя Ганкеля Н^р (й) =

В разделе 2.2 «Коммутативные образы кс-языков: связь с линейными языками» рассмотрен еще один подход к распознаванию коммутативных образов кс-языков. А именно, рассматривается и-кратный степенной ряд

«(*) = Х«^", (6)

ОГС/|

сходящийся в окрестности нуля, где а = (а^...,а„) — целочисленный мультиин-декс, а] > 0, ] = \,...,п, г = .....,гг)еС", /,= {а = (<*,,...,«„):аг, > 1} в предположении, что его сумма а(г) — коммутативный образ кс-языка.

Пусть степенной ряд

*(*,*„> = ЕХ«..а*а°а (7)

Сто ¿0,аге/]

также сходится в окрестности начала координат; здесь а0 — целочисленный скалярный индекс,

• г0 е С1, = .....• ■ • .

Коэффициенты коммутативных образов кс-языков от п переменных тесно связаны с коэффициентами коммутативных образов линейных языков от /7 + 1 переменного, а именно, имеет место следующая

ТЕОРЕМА 2.2. Для того чтобы голоморфная в окрестности нуля функция (6) являлась коммутативным образом кс-языка, достаточно существование голоморфной в окрестности начала координат рациональной функции (7) (являющейся коммутативным образом некоторого линейного язъ1ка), такой, что для всех ог = (от,,...,«„) выполнялось равенство аа = а, и необходимо

существование голоморфной в нуле рациональной функции (7) (коммутативного образа линейного языка), такой, что при всех а выполнялось равенство

аа=Кр[,р\0-аА> (8)

здесь (3 = (Д,..., Рп), А — унимодулярная матрица порядка п с неотрицательными целыми элементами.

Ряд (6) называется диагональю ряда (7), если при некоторой унимодуляр-ной матрице А для этих рядов выполнено условие (8).

Замечание. Если А = Е — единичная матрица, то условие (8) имеет вид

«« =К„а> а = («,,...,«„)•

В случае п — 1, тривиальном для теории языков, теорему 2.2 можно сформулировать следующим образом.

ТЕОРЕМА 2.2* .Для того, чтобы голоморфная в окрестности точки О е С1 функция

о

бша алгебраической, необходимо и достаточно существование симметричной относительно переменных Х\, рациональной функции

я(г„г2)= ЕЯм^2'

голоморфной в окрестности точки (0,0) е С2, такой, что

В разделе 2.2 также доказаны две важные леммы. Пусть г) — многочлен, который определяет алгебраическую функцию (6): м> = а(2),

Р(а(г), г) = 0. Согласно условию на индексы суммирования ряда (6), я(0,0) = 0, Р(0,0) = 0.

Ситуация, когда при исследовании кс-языка в качестве матрицы А можно выбрать наиболее простую — единичную матрицу, определяется следующим утверждением.

ЛЕММА 2.1. Пусть а(г) - коммутативный образ кс-языка, т.е. голоморфная в окрестности нуля функция, представленная рядом (б), и пусть многочлен Р(м>,г), определяющий функцию а(£), в окрестности нуля имеет вид

Р(-н>,г) = (-п>-а(г))ки(\у,г),

где и(м>,г) — обратимый росток кольца О ростков голоморфных в нуле функций. Тогда найдется голоморфная в окрестности начала координат рациональная функция К(г0,г), представленная рядом (7) (коммутативный образ линейного языка), такая, что для всех а = (а,,...,агп) выполнено условие

ао =л«„а-

В случае, когда условие леммы 2.1 не выполняется, через точку (0,0) может проходить несколько ветвей неявной функции, заданной уравнением Р(0,0) = 0, в связи с этим необходимо отделить голоморфную ветвь = а(г) от других ветвей функции, проходящих через начало координат. Это можно сделать с помощью частичного разрешения особенности гиперповерхности {Р(м>, ¿) - 0} в начале координат, а именно, подобрав бирациональную замену координат специального вида, отделяющего росток графика {и> = а(г)} от других неприводимых ростков аналитического множества {/>(0,0) = 0}.

В связи с этим вводится понятие разрешающего отображения для голоморфной ветви м> = а{х) неявной функции относительно уравнения Р(0,0) = 0; лемме 2.2 доказывается его существование.

При этом важно, что разрешение особенности использует лишь «односторонние» сг-процессы (мономиальные замены переменных специального ви-

да). В частности, при п = 1 кривая {Р(уу,г) = 0} «поднимается» на ту часть поверхности еС2 х />': - = 0}, которая записана в карте (системе координат) проективного пространства Р\ которая характеризуется условием <? = !•

Лемма 2.2 позволяет свести изучение коммутативного образа произвольного кс-языка к той ситуации, которая описана в условии леммы 2.1.

Теорема 2.2 связывает коммутативные образы кс- и линейных языков (соответственно, алгебраические и рациональные функции). Структура степенных рядов рациональных функций, являющих коммутативными образами линейных языков, достаточно хорошо изучена. Например, рациональность суммы

степенного ряда ^акгк эквивалента тому, что а к — <7 (к), к е N, где - ква-к

зимногочлен. Другим критерием рациональности, как отмечалось, является известный критерий Кронекера (равенство нулю определителей Ганкеля:

Известны также обобщения этого условия на кратные степенные ряды, которые получаются применением одномерного критерия по каждой переменной кратного ряда.

Таким образом, в диссертации предложены два критерия алгебраичности суммы степенного ряда (коммутативного образа формального языка).

В разделе 2.3 «Коммутативные образы кс-языков как диагонали рядов Лорана рациональных функций» рассмотрена процедура диагонализации для рядов "Лорана. В этом случае оказалось, что достаточно сложной процедуры разрешения особенностей, приводящей к мономиальной замене переменных с унимодулярной матрицей, можно не производить: в этом случае коммутативный образ кс-языка является диагональю относительно двух индексов рядов Лорана рациональной функции.

Показано также, что любой интеграл по остову (полукруговому множеству) от рациональной функции можно интерпретировать как диагональ ряда Лорана некоторой рациональной функции.

В разделе 2.4 «Конструктивное представление и приближенное вычисление коммутативных образов кс-языков» в качестве следствия результатов раздела 2.2 получены формулы для представления коммутативного образа кс-

языка рядом Лорана специального вида. Такое представление дает возможность приближенного вычисления коммутативного образа по отрезку этого ряда Лорана.

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

Действительно, решение произвольного алгебраического уравнения

Р{п,2) = гяуу" + ... + г,м> + 20 =0,

является ветвью алгебраической функции, следовательно, ее можно представить в виде диагонали степенного ряда определенной рациональной функции. Необходимый отрезок этого ряда дает необходимые формулы (фактически, по- ■ лученный ряд по переменной г! будет рядом Лорана). Заметим, что решение таких уравнений является одной из фундаментальных задач математики.

А именно, обозначим г = (г0,2,,...,гл), тогда, как показано в разделе 2.4, решение искомого уравнения получается в виде ряда:

+.:Т*„>1 (("-!)£„ +... + к2+\)\кг\.Лп

Конечный отрезок данного ряда, позволяет приближенно вычислять коммутативный образ кс-языка.

Раздел 2.5 «Фундаментальные свойства множеств сходимости коммутативных образов формальных языков» имеет вспомогательный характер. В нем рассмотрены свойства, которые имеют множества сходимости кратных степенных рядов (коммутативных образов кс-языков). Сходимость понимается в смысле существования конечного предела при суммировании по всевозможным многомерным параллелепипедам в области изменения индексов.

Изучение свойств таких множеств необходимо потому, что для кратного степенного ряда нет прямого обобщения классической леммы Абеля: из сходи-

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

Вопрос состоит в том, чтобы по сходимости ряда в некоторых точках оценить область голоморфности его суммы. Этот вопрос рассматривался в 6080-х прошлого века, однако некоторые важные особенности строения множества точек сходимости остались не изученными.

В разделе 2.5 получены следующие теоремы, которые могут быть полезны, например, при компьютерной проверке сходимости коммутативного образа формального языка.

ТЕОРЕМА 2.4. Если ряд

2Х*" (9)

а

сходится в области и в точке = (2,(0),...,г^0)), 0, у = 1 ,...,п, то он абсолютно сходится в области

С = Ц£>*иж1|)]п[(> е С": (г.....,[/]...,гя) е Г№*])}

Пример. Пусть п = 3, и ряд сходится в полной 3-круговой, логарифмически выпуклой области

£) = {г е С3 :| г, | +1 г2 | +1 г31< 1}, а также сходится в точке (1, 1, 1). Тогда, согласно теореме 2.4, этот ряд абсолютно сходится в более широкой области

£ = (I г1!+1г11+12з 1< 1;1I +1 1< 1}.

Теорему 2.4 можно считать многомерным аналогом леммы Абеля, а следующую теорему — дискретным аналогом теоремы о логарифмической выпуклости области (абсолютной) сходимости,

ТЕОРЕМА 2.5. Если степенной ряд (9) сходится в точках

. -к.

где | |> г^р привсех] = 1,...,п, то он сходится и в точке = (г,'01,..., г^01). Во

всех остальных точках, кроме точки 0, ряд может расходиться.

Глава 3 «Распознавание контекстно-свободных языков: необходимые условия» посвящена условиям, невыполнение которых свидетельствует о том, что формальный язык не является контекстно-свободным.

Так, в разделе 3.1 «Теорема Эйзенштейна для коммутативных образов кс-языков» обобщается известная теорема Эйзенштейна о степенных рядах алгебраических функций одного переменного на коммутативные образы кс-языков, что дает необходимое условие принадлежности формального языка классу кс-языков.

ТЕОРЕМА 3.1. Если сумма п-кратного степенного ряда

является коммутативным образом кс-языка, и аа - рациональные числа для всех а, то найдется целое число Ь--аО, такое, что числа являются це-

лыми при всех а.

В разделе 3.2 «Условия для коммутативных образов, сгруппированных по однородным многочленам» рассмотрено распределение нулей однородных многочленов коммутативного образа линейного языка. Соответствующие условия формулируются следующим образом.

Пусть сумма ряда по однородным многочленам

Ж) = !(/)*(*)

кг о

голоморфна в окрестности точки 0 е С". Ассоциируем с этим рядом множества

Nf ={z£.Cx:(f)k(2,\,■■■^) = Щ,Nf= и^/' и пусть А^ - совокупность пре-

<Л**о

дельных точек в С множества Nг .

Очевидно, что для любого замкнутого множества М а С найдется целая функция/(г), для которой Щ-М. Однако для коммутативных образов линейных языков имеет место свойство, которое сформулируем для п— 2.

ПРЕДЛОЖЕНИЕ 3.1. Пусть /(г,, г2) — коммутативный образ линейного языка, голоморфный в окрестности нуля. Тогда N'f с/иГ, где Г - конечное множество, а множество у имеет вид

т

м

где ф\,у/х,...,<рт,у/п — функции, аналитические вне множества Г.

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

В разделе 3.3 «Условия для коммутативных образов, сгруппированных в ряды Гартогса» приводятся соответствующие необходимые условия.

Глава 4 «Распознавание контекстно-свободных языков: достаточные условия для коммутативных образов» начинается разделом 4.1 «Достаточное условие алгебраического продолжения коммутативного образа языка». В нем рассмотрен вопрос о том, каково должно быть множество значений группы переменных, от которых зависит коммутативный образ кс-языка, для того, чтобы при фиксированных значениях переменных из этого множества его алгебраич-пость по другим переменным гарантировала алгебраичность при любых значениях переменных этой группы. При этом обобщена на алгебраические функции граничная теорема Э. Леви о рациональности по одному переменному. Полученная теорема показывает, что достаточно требовать алгебраичность исследуемого коммутативного образа языка только на части границы той области, в которой установлена его голоморфность.

ТЕОРЕМА 4.1. Пусть коммутативный образ формального ряда /(г',г„)

голоморфен в области £> = И' х Оп с-С"'1 хС^ и непрерывен в О , причем гра-

ница области Б' — кусочно гладкая. Предположим, что на границе дО' есть множество Е' положительной (2п — Ъ)-меры, такое, что при каждом фиксированном ¿¡' е Е' функция /(г',га) алгебраична по Тогда при каждом фиксированном эта функция также является алгебраической по переменной г„.

В разделе 4.2 «Композиция Адамара формальных языков и их коммутативных образов» рассматриваются вопросы, связанные с представлением коммутативных образов кс-языков в виде композиции Адамара двух коммутативных образов формальных языков. Такая конструкция играет важную роль в теории кс-языков, поскольку в определенных ситуациях позволяет представить исследуемый язык в виде «композиции» более простых языков.

В частности, рассматривается композиция Адамара

1№о

коммутативных образов двух формальных языков

/(*)= 2>в*в, (10)

Мао .

— и-кратных степенных рядов, сходящихся в окрестности начала координат.

Как известно, теорема Адамара об умножении особенностей позволяет по множествам особых точек функций Дг) и ¿(г) оценить множество особенностей композиции Адамара этих функций, а потому ей уделяется большое внимание в теории формальных языков. Действительно, если коммутативный образ такого языка удается представить в виде композиции Адамара коммутативных образов языков, особенности которых поддаются исследованию, то получается описание особенностей изучаемой функции, которое дает о ней значительную информацию. Композицию Адамара можно представить через исходные функции

при помощи интеграла по циклу, и исследование параметрического интеграла позволяет определить особенности исходных функций и их характер.

В предположении, что функции Дг) и g(z) являются коммутативными образами наиболее простых, линейных, языков, в разделе 4.2 изучен аналитический характер их композиции Адамара.

Обозначим Рт(С") класс всех функций, каждая из которых аналитична вне некоторой алгебраической гиперповерхности Vh cz С", и для всякого замкнутого пути yczC"\Vh и любого элемента этой функции в точке у(0) имеет место равенство

(T/-I)mh0= О

для некоторого положительного к = k(y,h0\ где Т — оператор аналитического продолжения элемента h0 вдоль пути у из точки у(0), а 7 - тождественный оператор. Классы таких функций называются классами Нильсена.

Согласно этому определению, алгебраические функции принадлежат классу Р1 (С"), а функция log" г, принадлежит классу Нильсена Рт+1(С"), но не принадлежит классу Рт(С").

Характер ветвления композиции Адамара описывает следующая теорема.

ТЕОРЕМА 4.2. Если (10) и (11) — коммутативные образы линейных языков, то их композиция Адамара IIf g(z) принадлежит классу Pn_t(C).

Поскольку обобщение композиции Адамара и теоремы об умножении особенностей рассматривается в главе 4 применительно к исследованию кс-языков, в разделе 4.3 «Кс-языки и композиция Адамара линейных языков» изучение композиции Адамара проводится для коммутативных образов таких языков. Как видно из теоремы 4.2, для коммутативных образов линейных языков (зависящих от многих переменных) композиция Адамара может также быть трансцендентной функцией. В связи с этим исследована композиция Адамара рациональных функций двух переменных: получено ее выражение через локальные вычеты специального вида, позволяющие провести полное исследование (вычеты Гротендика), найдена алгебраическая кривая ее особенностей, а в

разделе 4.4 «Характер особенностей композиции Адамара линейных языков» полностью изучен характер особых точек. Исследован случай, когда композиция Адамара линейных языков все же приводит к линейному языку.

Как следствие этих результатов, в разделе 4.5 получено полное описание свойств диагоналей коммутативных образов линейных языков (процедура диа-гонализации степенного ряда представляет значительных интерес в теории формальных грамматик).

В разделе 4.6 «Композиция Адамара сгруппированных линейных языков» исследование проводится применительно к рядам по однородным многочленам: соответствующий аналог композиции Адамара может быть использован применительно к линейным языкам.

В главе 5 «Вычислительное распознавание контекстно-свободных языков и грамматик» основные полученные результаты применяются к распознаванию кс-языков и грамматик, а также изучению их фундаментальных свойств.

В разделе 5.1 «Решение проблемы вычислительного распознавания коммутативных образов кс-языков» приводится соответствующий вычислительный алгоритм.

Рассмотрим этот алгоритм применительно к степенному ряду с одной переменной

<з00=1>*2* .

ш

Пусть задан общий вид коэффициентов этого ряда о* как функции номера к. Тогда необходимо:

1) вычисляя определители Ганкеля как функции номеров /, к, проверить, равны ли они нулю;

2) в случае неравенства вычислить коэффициенты как функции номера и проверить, равны ли нулю значения обобщенных определителей Ганкеля Я)'Ч2);

3) вычислить для следующего значения г коэффициенты а^ и проверить выполнение равенства нулю обобщенных определителей Ганкеля +1).

Вычисления продолжатся до тех пор, пока не будет установлено обращение в нуль требуемых определителей, либо будет установлено, что они как функции номеров не равны нулю - последнее означает, что функция трансцен-дентна. Таким образом, алгоритм дает принципиальную возможность установить алгебраичность функции одной переменной.

Более того, указанный алгоритм приводит к алгоритму полного исследования свойств этой алгебраических функций. Для этого необходимо:

1) установить алгебраичность исследуемой функции с помощью равенства нулю чисел H^id);

2) равенства нулю определителей означают, что соответствующая однородная система линейных алгебраических уравнений имеет ненулевое решение; его компонентами являются коэффициенты многочлена, который определяет эту функцию, а значит, решение системы восстанавливает этот многочлен;

3) полученный многочлен содержит полную информацию о свойствах исходной функции (например, обращается ли эта функция при некоторых конечных значениях в бесконечность, имеются ли другие ветви этой функции, голоморфные в точке нуль) и дает принципиальную возможность их исследовать.

Далее, полученный критерий дает принципиальную возможность установить алгебраичность коммутативного образа

ci{r) = 2>tz*, к

где

akzk=ak......ак=

#*,(»,)=*,.....#*„(w,)=*„

кс-языка

г = r»wi > ■

Действительно, перегруппировывая ряд коммутативного образа ci(r) в ряд Гартогса по одной из переменных, можно применить алгоритм исследова-

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

В разделе 5.2 «Аффинные кс-грамматики и кс-языки» введен и изучен важный класс кс-грамматик. Рассмотрим систему полиномиальных уравнений (4), определяющую кс-язык, а также ее подсистему

д,(х,г) = 0, / = 2,...,тп, (12)

считая л: и гх параметрами, а корни этой системы 2[1] = (22,...,гя)= за-

висящими от этих параметров. При этом удобно рассматривать корни г[1](лс, г,) в проективном пространстве С/1"^1, а параметры - в пространстве С". В таких координатах система имеет вид

Ьо ьо

где V, = с1ецг[цд^х,г), а - координаты проективного простран-

ства СРтЧ. При = 0 корни системы (4) расположены в пространстве Ст'1 — аффинной части СРт'1, а при = 0 - на бесконечноудаленной гиперплоскости пространства СРт']. Бесконечноудаленные корни системы (4) — при = 0 — совпадают с корнями системы

*;(*,*„£) = 0,1 = 2.....и, (13)

где д\(х,г) — старшая однородная составляющая многочлена д,(х<г) по переменной г[1] с коэффициентами, зависящими отх и г1> а - (£2,...,£т).

Если многочлены последней системы не зависят от х и 2\, и она имеет только единственный корень = — = =0, при =0 не определяющий точки в проективном пространстве, то будем называть аффинным языком кс-язык,

определяемый системой уравнений (4), поскольку в этом случае соответствующая ей подсистема уравнений (13) не имеет бесконечноудаленных корней, следовательно, ее корни могут быть расположены лишь в аффинной части проективного пространства.

Для определения свойств грамматики важно установить, когда многочлен Г(х,21), определяющий алгебраическую функцию г, (х) — первую компоненту решения (2|(х),...,гт(х)) системы (4), Р(х,г{(х)) = О, Р(0,0), обладает свойством Р(0,0) Ф 0. Имеет место следующая

ЛЕММА 5.1. Пусть система (13) не зависит от х и 2\ и имеет единственный корень £ = 0. Тогда можно выбрать многочлен Р(х,г,), определяющий

алгебраическую функцию г, = г, (х), такой, что

&,

Из этого утверждения вытекает следующая теорема.

ТЕОРЕМА 5.1. Для любого аффинного кс-языка над терминальным множеством X существует линейный язык Ь(х0,х)над терминальным множеством {х0} и X, такой, что

«'(г, (х)) = Л^ (а(Цх0, х,))), (14)

где А^ нЫ(Ь(хй,х)) — диагональ ряда сг'(/,(х0,х)) по переменным х0,х1.

Если записать в явном виде коэффициенты степенных рядов голоморфных функций а'(г1 (х)) и <?г(£(х0, х)), то получим следующую теорему.

ТЕОРЕМА 5.2. Для любого кс-языка над терминальным множеством X

существует линейный язык ^l<L,uJ■ >и} над терминальным множеством

1

{х0}иХ, такой, чтопривсех кх,...,кт £0 выполнены равенства

■№,->= Х<1'и)> о5)

(»< .-!*хт (»1 )=*™ ("у )-*1 .".#*т (^^J)=Ь„,,ltx0(uJ)^^^tx¡(UJ)

Теорема 5.2 дает необходимое условие того, что данный формальный ряд г, (х) является аффинным кс-языком: если возможно показать, что ни для какой рациональной Цх0,х) функции равенство (15) или равенство

с'(г,(х)) = ЛГоХ1С1(Цх0,х))) не выполняются, то этот ряд не принадлежит классу аффинных кс-языков.

При выполнении равенства (14) назовем ряд г,(х) коммутативной (слабой) диагональю ряда Ь(х0, х). Если же выполнено равенство

Х< >>ч = Х< ¿.«у > и - >

где е — пустая цепочка, то назовем ряд г, (х) некоммутативной (сильной) диагональю ряда Ь{х0,х) и будем записывать г,(х) = (Ь(х0,х)). Ясно, что при переходе к сильной диагонали ряда утрачивается меньше информации о нем, чем при переходе к слабой диагонали.

Имеет место следующее утверждение.

ПРЕДЛОЖЕНИЕ 5.1. Для того чтобы язык г,(х) был аффинным кс-языком, необходимо и достаточно, чтобы он был некоммутативной (сильной) диагональю линейного языка над множеством {х0} ^ X.

Таким образом, имеется еще один, кроме применения теорем 2.1 и 2.2, путь распознавания кс-языков: по общему виду коэффициентов исследуемого языка подобрать язык большей размерности, диагональю которого является исходный, проверить полученный язык на линейность с помощью критерия Кро-некера о рациональности, тогда язык является аффинным кс-языком.

Предложение 5.1 описывает фундаментальное свойство аффинных кс-языков, связанное со свойствами системы Хомского-Щютцснберже: кс-языки выражаются через языки принципиально более простого класса (от большого числа символов) при помощи простой процедуры диагонализации.

Замечание. При рассмотрении аффинных кс-языков и при получении некоторых других результатов настоящей диссертационной работы в значительной мере решается проблема определения свойств кс-языка по свойствам символьной системы уравнений Хомского-Щютценберже. Например, показано, что

свойства кс-языка во многом зависят от свойств корней соответствующей системы полиномиальных уравнений от многих переменных.

ОСНОВНЫЕ РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Сафонов К.В. О множестве точек сходимости двойного степенного ряда // Известия вузов. Математика. - 1982. — № 6. — С. 48—52.

2. Сафонов К.В., Цих А.К. Об особенностях параметрического вычета Гротендика и диагонали двойного степенного ряда // Известия вузов. Математика. - 1984. - № 4. - С. 51-58.

3. Сафонов К.В. Об особенностях двумерной композиции Адамара (Аннотация статьи) // Сибирский математический журнал. - 1985. - № 4. - С. 200.

4. Сафонов К.В. Об условиях алгебраичности и рациональности суммы степенного ряда // Математические заметки. - 1987. — Т. 41. — Вып. 3. - С. 325— 332.

5. Safonov K.V. Holomorphic extension of two-dimensional Hadamard Product // Selecta Mathematica Soviética. - 1989. - V. 8. - № 1. - Pp. 23-30.

6. Сафонов К.В. Монодромия композиции Адамара рациональных функций / Вопросы математического анализа: Сборник научных статей. - 1992. — Красноярск. — С. 63—67.

7. Сафонов К.В. О кратных степенных рядах неявных и мероморфных . функций многих переменных / Вопросы математического анализа: Сборник научных статей. - 1995. — Красноярск. - С. 93-105.

8. Сафонов К.В. Степенные ряды неявных и мероморфных функций многих переменных / Международная конференции «Математические модели и методы их исследования». - 1997. - Красноярск. - С. 162-163.

9. Сафонов К.В. О порядках алгебраичности аналитических функций / Третий Сибирский конгресс по прикладной и индустриальной математике. -1998. - Новосибирск. - С. 92-93.

10. Сафонов К.В. О кратных степенных рядах алгебраических и рациональных языков / 5-й Международный семинар-совещание «Кубатурныс формулы и их приложения». - 1999. - Красноярск. — С. 33-34.

11. Safonov K.V. On power series of algebraic and rational functions in С" H Journal of Mathematical Analysis and Applications. - 2000. - V. 243. - Pp. 261-277.

12. Сафонов К.В. О кратных степенных рядах алгебраических и рациональных языков / Труды Международной конференции «Комплексный анализ и дифференциальные операторы», посвященной 150-летию C.B. Ковалевской. -2000.-Красноярск.-С. 127-133.

13. Сафонов К.В. Ряды Тейлора алгебраический функций как диагонали рядов Лорана рациональных функций / Многомерный комплексный анализ: Сборник научных статей. — 2002. —Красноярск. — С. 158—164.

14. Сафонов К.В. О распознавании контекстно-свободных грамматик // Вестник Томского государственного университета. Серия «Математика. Кибернетика. Информатика» - 2003. - Прил. № 6. - С. 16-18.

15. Сафонов К.В. О представлении решений произвольных алгебраических уравнений рядами Лорана / Вопросы математического анализа: Сборник научных статей. - 2004. — Красноярск. - С. 129-132.

16. Сафонов К.В. Контекстно-свободные языки как диагонали линейных языков // Вестник Красноярского государственного технического университета. - 2004. - Вып. 33. - Красноярск. - С. 37-41.

17. Сафонов К.В. Проблемы синтаксического анализа и распознавания контекстно-свободных языков / Вопросы математического анализа: Сборник научных статей. - 2005. — Красноярск. - С. 143 - 155.

18. Сафонов К.В. Обобщение критерия Кронекера о рациональности суммы степенного ряда на алгебраические функции и его применение // Вестник

Красноярского государственного университета. Серия физ.-мат. науки. — 2005, № 1 - С. 76-80.

19. Сафонов К.В. Распознавание аффинных контекстно-свободных языков // Вестник Томского государственного университета. Серия «Математика. Кибернетика. Информатика» - 2005. - Прил. № 14. — С. 26-30.

18. Сафонов К.В. О возможности вычислительного распознавания контекстно-свободных грамматик // Вычислительные технологии. — 2005. - Т. 10. — №4.-С. 91-98.

21. Сафонов К.В. О синтаксическом анализе и свойствах формальных языков программирования // Вычислительные технологии. — 2005. - Т. 10. -Специальный выпуск. - С. 10-15.

22. Сафонов К.В. Аналитический подход в теории формальных языков программирования / Интеллект, управление, информационные технологии: Материалы всероссийской конференции «Математика, информатика, управление». Ч. 2 - Иркутск. - 2005. - С. 228-232.

Соискатель:

Отпечатано в ИПЦ КГТУ. Тираж 120 экз. Заказ 674/2 660074, Красноярск, ул. Киренского, 28

ВВЕДЕНИЕ.

0.1. Проблематика исследования.

0.2. О содержании диссертации.

ВСПОМОГАТЕЛЬНАЯ

ГЛАВА.

ГЛАВА 1. Контекстно-свободные языки, их синтаксический анализ и коммутативные образы.

1.1. Контекстно-свободные грамматики и порождаемые ими языки.

1.2. Идентификаторы языков программирования и их задание контекстно-свободными грамматиками.

1.3. Проблема синтаксического анализа кс-языков программирования.

1.4. Коммутативные образы (производящие функции) кс-языков.

ГЛАВА 2. Фундаментальные свойства коммутативных образов контекстно-свободных языков.

2.1. Решение проблемы установления алгебраичности суммы степенного ряда (коммутативного образа формального языка).

2.2. Коммутативные образы кс-языков: связь с линейными языками.

2.3. Коммутативные образы кс-языков как диагонали рядов Лорана рациональных функций.

2.4. Конструктивное представление и приближенное вычисление коммутативных образов кс-языков.

2.5. Фундаментальные свойства множеств сходимости коммутативных образов формальных языков.

ГЛАВА 3. Распознавание контекстно-свободных языков: необходимые условия.

3.1. Теорема Эйзенштейна для коммутативных образов кс-языков.

3.2. Условия для коммутативных образов, сгруппированных по однородным многочленам.

3.3. Условия для коммутативных образов, сгруппированных в ряды Гартогса.

ГЛАВА 4. Распознавание контекстно-свободных языков: достаточные условия для коммутативных образов.

4.1. Достаточное условие алгебраического продолжения коммутативного образа языка.

4.2. Композиция Адамара формальных языков и их коммутативных образов.

4.3. Кс-языки и композиция Адамара линейных языков.

4.4. Характер особенностей композиции Адамара линейных языков.

4.5. Диагонали линейных языков.

4.6. Композиция Адамара сгруппированных линейных языков.

ГЛАВА 5. Вычислительное распознавание контекстно-свободных языков и грамматик.

5.1. Решение проблемы вычислительного распознавания коммутативных образов кс-языков.

5.2. Аффинные кс-грамматики и кс-языки.

5.3. Опеределители Ганкеля и алгебраическая зависимость кс-языков.

0.1. Проблематика исследования

Фундаментальным свойством большинства языков программирования является принадлежность классу контекстно-свободных языков (кс-языков), которые были введены в 50-х годах прошлого века выдающимся американским лингвистом Н. Хомским, заложившим основы теории кс-языков [113-119]. Действительно, в описании языка программирования определяются действующие в нем правила подстановки (продукции), совокупность которых является контекстно-свободной грамматикой (кс-грамматикой), порождающей соответствующий кс-язык программирования (напр., [5-8,14, 22, 26, 27, 39, 41, 42, 46, 49, 53, 60, 65, 68, 70, 120]). Таким образом, основные аспекты проблематики, связанной с исследованием различных языков программирования (к их числу относятся проблемы определенности языка, его синтаксического и семантического анализа и др.), могут быть рассмотрены с общей точки зрения, а именно, применительно к изучению свойств кс-языков, определяемым следующим образом.

Пусть конечное множество X = . ,хп] терминальных символов (слов) языка, например, операторов языка программирования, букв, цифр и т.д., а У = {у1,. ,ут} — множество нетерминальных символов, необходимых для задания грамматики языка, у\ — символ (аксиома), означающий начало программы (предложения); на множестве X и У введены операции конкатенации и формальной суммы, а также умножения на элементы числового поля.

Рассмотрим кс-язык, порожденный совокупностью продукций (грамматикой):

У; ¡ц(х,у),.,у{ -)• ¡щ(х,у), г = 1,. ,т, (0.1) где /у (ж, у) - мономы от некоммутативных символьных переменных из X и У (левая часть продукций содержит единственный символ и применяется независимо от контекста, а потому грамматика называется кс-грамматикой); как отмечалось, у\ — выделенный символ, означающий начало программы (предложения).

Тогда грамматике сопоставляется система полиномиальных символьных уравнений у{ =р1(х,у), % = 1,.,т, (0.2) где

Рг(х,у) = /й(х,у) + . . . + /щ(х,у), которую будем называть системой уравнений Хомского-Щютценберже (грамматикой в форме Хомского-Щютценберже).

Пусть < г,ги > обозначает числовой коэффициент, с которым моном гу от некоммутативных переменных входит в формальный ряд или многочлен г. Система (0.2) называется собственной системой, если ее коэффициенты удовлетворяют следующим условиям. А именно, порождающая способность грамматики не уменьшится, если из правил подстановки исключить правила вида у; и у1 -> е, где е — пустая цепочка (играющая роль единицы относительно умножения мономов: ех = хе = х), что и приводит к возможности [149] рассматривать только собственные системы (0.2), правые части которых удовлетворяют условиям

Р1,е >= 0,<Рг,У] >= о, 1,3 = 1 ,.,771. (0.3)

Метод последовательных приближений для системы (0.2) состоит в следующем. Рассмотрим итерации символьного решения системы:

Г'=Й(«,»(Ч),»(Ч = (»}",.,®й>), к = 0,1./> = (0,.,0), которые дают, в частности, выражение переменной у\ (кс-языка) в виде формального степенного ряда

У\ = ^ < > Щ. (0.4) г

Первая компонента у\ решения (у1(х),. ,ут(х)) системы (0.2), полученного методом последовательных приближений в виде формальных степенных рядов от х\,.,хп является данным кс-языком, т.е. формальной суммой мономов — всех правильных предложений (программ) данного языка.

Мономы г^ от XI,. ,хп этого ряда являются всевозможными правильными предложениями (программами) этого языка, причем числовой коэффициент < т/1, г^ > при мономе равен числу выводов этого монома при всевозможных применениях грамматических правил [102].

Важнейший подкласс кс-языков образуют линейные, в частности, регулярные языки, для которых все многочены системы (0.2) — линейные, в частности, леволинейные по у] = 1,., т.

Пример. Рассмотрим собственную систему

2/1 = ад + жш,

У2 = %2У2Х3 + Х2Х3, для которой метод последовательных приближений дает решение:

Нетрудно проверить, что первая компонента решения представляется рядом таким образом, данный кс-язык (над словарем {х1,х2,хз}) состоит из предложений вида

В исследованиях кс-языков и кс-грамматик основную роль играли методы дискретной математики, например, анализ деревьев вывода мономов. При этом изучение системы (0.2), которая содержит всю информацию о кс-языке, не проводилось. Прежде всего это было связано с недостаточно разработанными методами многомерного комплексного анализа, позволяющими исследовать символьные решения системы (0.2). Несмотря на значительные результаты многие проблемы не были решены.

До сих пор теория формальных языков (программирования) не дала ответ на следующий фундаментальный вопрос: каковы свойства кс-языка, как по заданному формальному ряду (0.4) определить, является у(0) = (0,0), у{1) = (0;зд), У{2) = (х1х2хз]х1х1 + х2х3), У® = {Х1Х2ХЗ + Х\х\х\ + х\х\ + х\х\),--- ли он кс-языком, т.е. порожден ли он кс-грамматикой - некоторой полиномиальной системой уравнений вида (0.2)? Как отличить его от формального набора мономов, не являющегося кс-языком (программирования)?

Заметим, что если набор мономов из терминальных символов конечен, то ответ тривиальный: существует конечный кс-язык

У1 —> - -., 2/1 —> равный формальной сумме этих мономов, а потому имеет смысл рассматривать вопрос лишь о бесконечном формальном языке.

В исследованиях, посвященных изучению проблем, связанных с классом кс-языков, указанный вопрос не изучен. Эти исследования были направлены, например, на решение следующих проблем: по заданной кс-грамматике в форме Хомского-Щютценберже, т.е. по коэффициентам заданной системы уравнений (0.2), определить, содержит ли порождаемый ею кс-язык заданный моном с ненулевым коэффициентом (алгоритмически разрешимая проблема), порождают ли две заданные грамматики, а фактически - две различные системы уравнений вида (0.2), один и тот же кс-язык (как оказалось, алгоритмически не разрешимая проблема) и др.

Исследователи неоднократно подчеркивали необходимость рассмотрения вопроса о характеризации (распознавании) кс-языков. Фактически, проблема распознавания кс-языков восходит к работам академика В.М. Глушкова (например, [39]), который писал, что при решении проблем теории кс-языков важно иметь критерии, с помощью которых можно выяснить, является ли данный язык контекстно-свободным или нет [39, с. 197].

При этом В.М. Глушков и его ученики уделяли большое внимание необходимым и, отдельно, достаточным условиям, позволяющим в определенных случаях установить принадлежность языка классу кс-языков.

Однако, несмотря на значительное число результатов, посвященных кс-языкам [25-38, 51, 58, 59, 78, 106, 125, 141-144, 153-158, 162-167], какие-либо условия, характеризующие эти языки (соответствующие формальные ряды), не были известны (исключение составляет, пожалуй, необходимое условие, которое дает лемма Бар-Хиллела [9]). Таким образом, одно из центральных понятий в теории программирования, а именно, понятие кс-языка, в течение полувека оставалось не достаточно изученным. В связи с изложенным необходимо сформулировать и рассмотреть проблему В.М. Глушкова распознавания кс-языков Хом-ского.

Применение методов дискретной математики не позволило решить целый ряд важных проблем, например, проблему беступикового синтаксического анализа таких языков, проблему изучения свойств таких языков по свойствам системы уравнений Хомского-Щютценберже (0.2) и многие другие.

Одним из основных препятствий для решения вопроса о характе-ризации (распознавании) кс-языков является тот факт, что и в более простом для исследования случае коммутативных переменных не было известно решение подобного вопроса, т.е. не были известны критерии, распознающие степенные ряды алгебраических функций.

В случае комплексных переменных у £ Ст,х £ Сп собственная система (0.2) имеет в окрестности нуля (0,0) £ (£т+п единственное голоморфное решение (у\(х),. ,ут{х)), компоненты у^х) которого — алгебраические функции. Действительно, записывая систему (0.2) в виде

Ф, у) = Уг~ Р»(®, У) = 0, г = 1,., т, (0.5) видим, что условия (0.3) равносильны тому, что

0,0) = 0,г = 1 = 5 дУз где 5ц - символ Кронекера, следовательно, собственная система удовлетворяет условию теоремы о неявном отображении (метод последовательных приближений дает в этом случае тейлоровские разложения голоморфных в окрестности нуля функций у{(х), % = 1,., т).

В настоящей диссертации на основе полученных новых результатов в области комплексного анализа получены новые методы распознавания кс-языков и изучения их свойств, что имеет значительную актуальность в теории программирования.

Цель работы состоит в получении новых методов распознавания кс-языков (в том числе, языков программирования) и изучения их свойств на основе исследования определяющей системы (0.2).

Методика исследования состоит в использовании методов алгебры, комплексного анализа и теории формальных грамматик.

Основные результаты диссертации состоят в следующем:

1. Решена проблема В.М. Глушкова распознавания кс-языков Хом-ского (в том числе, языков программирования), указаны соответствующие вычислительные алгоритмы.

2. Получен ряд новых необходимых, а также достаточных условий принадлежности формального языка классу кс-языков.

3. Разработан алгоритм беступикового синтаксического анализа кс-языков (языков программирования), основанный на предложенном автором методе "мономиальных меток".

4. Решена проблема установления алгебраичности суммы степенного ряда — доказан критерий алгебраичности, обобобщающий известный критерий Кронекера о рациональности суммы степенного ряда (1881 г.); полученный результат используется в диссертации при исследовании кс-языков.

5. В соответствии со свойствами системы (0.2) введен широкий класс (нелинейных) аффинных кс-языков, для которых доказано, что они образуются из линейных языков над более широким терминальным множеством в результате простой "процедуры диагонализации"; тем самым частично решена проблема определения свойств кс-языка по системе уравнений Хомского-Щютценберже.

Все основные результаты диссертации являются новыми.

Теоретическая значимость. Полученные в диссертации результаты существенно развивают теорию кс-языков программирования. Они доказаны новыми для этой теории методами, которые могут быть полезными и в дальнейших исследованиях.

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

Апробация работы. Результаты диссертации докладывались на научно-исследовательских семинарах в Красноярском государственном техническом университете, Красноярском, Новосибирском. Томском государственных университах, Институте математики им. С.Л. Соболева СО РАН, Институте динамики систем и теории управления СО РАН, на Всесоюзных, Всероссийских и международных коферен-циях по комплексному анализу и его приложениям (1982-2003 г.г.), на Сибирских конгрессах по индустриальной и прикладной математике (1998 г., 2000 г.), на Международных и Всероссийских конференциях по математическим моделям и методам их исследования (1997-2003 гг.), на Сибирских научных школах-семинарах с международным участием по проблемам компьютерной безопасности и криптографии (2003 г., 2005 г.).

Публикации. По теме диссертации опубликовано более 30 работ, наиболее значительные из которых приведены ниже, из них 10 работ опубликованы в журналах, которые включены ВАК в Перечень ведущих научных рецензируемых изданий, а также в иностранных научных рецензируемых журналах.

0.2. О содержании диссертации

1. Адаменко А.Н., Кучуков A.M. Логическое управление программирование и Visual Prolog. - СПб.: БХВ-Петербург. - 2003. - 992 с.

2. Айзенберг Л.А., Лейнартас Е.К. Многомерная композиция Ада-мара и ядра Сеге // Сиб. матем. журн. 1983. - Т. 24, No 3. - С. 3-10.

3. Айзенберг Л.А., Южаков А.П. Интеграьные представления и вычеты в многомерном комплексном анализе. Новосибирск: Наука. - 1979. - 366 с.

4. Арнольд В.И., Варченко А.Н., Гусейн-Заде С.М. Особенности дифференцируемых отображений. Т. 2. М.: Наука. - 1983. -335 с.

5. Арутюнова Н.Д. Предложение и его смысл. Логико-семантические проблемы. М.: Наука. - 1976. - 380 с.

6. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. М.: Вильяме. - 2001. - 135 с.

7. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир - 1978. - 352 с.

8. Ахо А., Хопфорт Д.Э., Ульман Дж. Структура данных и алгоритмы. М.: Вильяме. - 2000. - С. 225-257.

9. Бар-Хиллел И., Кашер А., Шамир Е. Меры синтаксической сложности. Кибернетический сборник. Нов. серия. Вып. 4. - Мир. -1967. - С. 219-227.

10. Бауэр Ф.Л., Гооз Г. Информатика. Т. 1. М: Мир. - 1990. - 324 с.

11. Бауэр Ф.Л., Гооз Г. Информатика. Т. 2. М.: Мир. - 1990. - 410 с.

12. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Т. 2.- М.: Наука. 1965. - 294 с.

13. Белецкий М.И. Бесконтекстные и доминационные грамматики и связанные с ними алгоритмические проблемы / Кибернетика. Вып. 4. 1967. - С. 90-97.

14. Белоногов Г.Г., Кузнецов Б.А. Языковые средства автоматизированных информационных систем. М.: Наука. - 1983. - 380 с.

15. Беляев В.А. К вопросу о множествах сходимости двойных степенных рядов // Матем. сб. 1966. - Т. 71. N0 1. - С. 14-23.

16. Беляев В.А. О множествах сходимости и абсолютной сходимости степенных рядов многих переменных / Исследов. по соврем, пробл. конструктивн. теории функций: сборник научных трудов.- Баку: АН Азерб. ССР. 1965. - С. 407-412.

17. Бибербах Л. Аналитическое продолжение. М.: Наука. - 1967. -237 с.

18. Бохнер С., Мартин У.Т. Функции многих комплексных переменны. М.: ИЛ. - 1953. - 300 с.

19. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь. - 1987. - 122 с.

20. Брюно А. Локальный метод нелинейного анализа дифференциальных уравнений. М.: Наука. - 1979. - 259 с.

21. Ван-дер-Варден Б.Л. Алгебра. М.: Наука. - 1973. - 368 с.

22. Вирт Н. Алгоритм + структуры данных = программы . М.: Мир. - 1985. - 342 с.

23. Владимиров B.C. Методы теории функций многих комплексных переменных . М.: Наука. - 1964. - 410 с.

24. Воробьев H.H. Теория рядов. М.: Наука. - 1975. - 368 с.

25. Гинзбург С., Грейбах Ш. Об инвариантности классов Нс-языков относительно некоторых отображений / Кибернетический сборник. Нов. серия. Вып. 5. - М.: Мир. - 1968. - С. 167-188.

26. Гинзбург С., Райе X. Два класса языков типа АЛГОЛ / Кибернетический сборник. Нов. серия. Вып. 6. - 1969. - С.114-145.

27. Гинзбург С., Роуз Дж. Характеристика машинных отображений / Кибернетический сборник. Нов. серия. Вып. 5. - 1968. - С. 128-137.

28. Гинзбург С., Роуз Дж. Об инвариантности классов относительно некоторых преобразований / Кибернетический сборник. Нов. серия. Вып. 5. - 1968. - С. 138-166.

29. Гинзбург С. Математическая теория контекстно-свободных языков. М. Мир. - 1970. - 325 с.

30. Гладкий A.B. Грамматики с линейной памятью // Алгебра и логика. 1963. - Т. 2. Вып. 5. - С. 43-55.

31. Гладкий A.B. Алгоритмическая природа инвариантных свойств грамматик непосредственно составляющих // Алгебра и логика. 1964. - Т. 3. Вып. 2. - С. 17-32.

32. Гладкий A.B. О сложности выводов в грамматиках непосредственно составляющих // Алгебра и логика. 1964. - Т. 3. Вып. 5-6. - С. 29-44.

33. Гладкий A.B. Некоторые алгоритмические проблемы для КС-грамматик // Алгебра и логика. 1965. - Т. 4. Вып. 1. - С. 3-13.

34. Гладкий A.B. Агоритмическая нераспознаваемость существенной неопределенности КС-языков // Алгебра и логика 1965. - Т. 4. Вып. 4. - С. 53—64.

35. Гладкий A.B. Прямое доказательство теоремы Мэтьюза // Алгебра и логика. 1965. - Т. 4. Вып. 5. - С. 60-70.

36. Гладкий A.B. Лекции по математической лингвистике для студентов НГУ. Новосибирск: НГУ. - 1966. - 256 с.

37. Гладкий A.B., Мельчук И.А. Элементы математической лингвистики. М.: Наука. - 1969. - 436 с.

38. Гладкий A.B. Формальные грамматики и языки. М.: Наука. -1973. 337 с.

39. Глушков В.М., Цейтлин Г.Е., Ющенко E.J1. Алгебра, языки, программирование. Киев: Наукова думка. - 1974. - 328 с.

40. Грифитс Ф., Харрис Дж. Принципы алгебраической геометрии. Тт. 1, 2. М.: Мир. - 1982. - 852 с.

41. Демьянков В.З. Специализированные теории интерпретации в вычислительной лингвистике. М.: МГУ. - 1988. - 87 с.

42. Демьянков В.З. Универсальная грамматика. Краткий словарь когнитивных терминов / Кубрякова Е.С., Демьянков В.З., Панкрац Ю.Г., Лузина Л. Г./ Под общ. ред. Е.С. Кубряковой. М.: МГУ. - 1996. - С. 181-185.

43. Диковский А.Я. О соотношении между классом всех контекстно-свободных языков и классом детерминированных контекстно-свободных языков // Алгебра и логика. — 1969. Т. 7. Вып. 1. - С. 34-42.

44. Диковский А.Я., Модина Л.С. Минимизация одной функции сложности в классе МП-автоматов и категориальные грамматики сложности три // Алгебра и логика. — 1968. Т. 7. Вып. 3. -С. 23-37.

45. Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука. - 1977. - 285 с.

46. Ершов А.П. Программирующая программа для быстродействующей электронной счетной машины. М.: Изд-во АН СССР. -1958. - 325 с.

47. Жданов О.Н., Цих А.К. Исследование кратных интегралов Меллина-Барнса с помощью многомерных вычетов // Сиб. ма-тем. журнал. Т. 39. No 2. - 1998. - С. 24—32.

48. Знаменский C.B., Майергойз JI.C. О степенных рядах от многих комплексных переменных / Голоморфные функции многих комплексных переменных: Сборник научных трудов. Красноярск, Ин-т физики СО АН СССР - С. 185-195.

49. Искусственный интеллект. Книга 2. Модели и методы: Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь. - 1990. - 304 с.

50. Карпов Ю.Г. Теория и технология программирования. Основы построения трансляторов. СПб.:БХВ-Петербург. - 2005. - 272 с.

51. Кибрик А.Е. Проблема синтаксических отношений в универсальной грамматике. Вып. XI. М.: Прогресс. - 1982. - С. 5-36.

52. К лини С.К. Представление событий в нервных сетях и конечных автоматах / Автоматы: сборник научных трудов. М.: ИЛ. -1956. - С. 15-67.

53. Компаниец Р.И., Маньков Е.В., Филетов И.Е. Системное программирование. Основы построения трансляторов. СПб: Коро-напринт. - 2000. - 256 с.

54. Кони И.М., Элгот К.С., Райт Д.Б. / Кибернетический сборник. Нов. серия. Вып. 3. М.: ИЛ. - 1961. - С. 147-166.

55. Курош А.Г. Курс высшей алгебры. M.-JL: Гостехиздат. - 1962.- 347 с.

56. Лейрнатас Е.К. Об одном обобщении композиции Адамара на функции многих комплексных переменных // Сиб. матем. журн.- Т. 22. No 4. 1981. - С. 218-221.

57. Лейрнатас Е.К. Об одном обобщении композиции Адамара в Сп.- Матем. заметки. Т. 32. - 1982. - С. 477-482.

58. Летичевский А.А. Представление контекстно-свободных языков в автоматах с памятью типа push-down / Кибернетика. Вып. 2. -1965. С. 80-84.

59. Летичевский А.А. Синтаксис и семантика формальных языков / Кибернетика. Вып. 4. - 1968. - С. 71-79.

60. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы проектирования компиляторов. — М.: Мир 1979. - 288 с.

61. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука.- 1965. 336 с.

62. Мамфорд Д. Алгебраическая геометрия. Т. 1. Комплексные проективные многообразия. М.: Мир. - 1979. - 256 с.

63. Маричев О.И. Метод вычисления интегралов от специальных функций. Минск: Наука и техника. - 1978. - 354 с.

64. Марков A.A. Теория алгорифмов. JI.-M.: Изд-во АН СССР. -1954. - 376 с.

65. Мартыненко Б.И. Языки трансляции. СПб.: СПбГУ. - 2004. -234 с.

66. Миролюбов A.A., Солдатов М.А. Линейные однородные разностные уравнения. М.: Наука. - 1981. - 208 с.

67. Мэтьюз Д. Разрывность и асимметрия в грамматиках непосредственно составляющих / Математическая лингвистика. М.: Мир. - 1964. - С. 150-159.

68. Наур Н. Алгоритмический язык АЛГОЛ-бО / Пересмотренное сообщение. М.: Мир. - 1965. - 245 с.

69. Никитина С.Е. Семантический анализ языка науки. М.: Наука. - 1987. - 128 с.

70. Опалева Э. Языки программирования и методы трансляции. -СПб.: BHV. 2005. - 480 с.

71. Ope О. Теория графов. М.: Наука. - 168 с.

72. Пассаре М., Цих А.К., Чешель A.A. Кратные интегралы Меллина-Бариса как периоды многообразий Калаби-Яу с несколькими модулями // Теор. и матем. физика. Т. 109. N0 3. - 1996. - С. 381-394.

73. Поляков В.Н. Синтез формальных моделей языка и смысла как проблема семантической обработки естественного языка // Новости искусственного интеллекта. 1997. N0 1. - С. 6-63.

74. Поспелов Д.А. Прикладная семантика и искусственный интеллект // программные продукты и системы. 1996. - N0 3. - С. 24-28.

75. Поспелов Д.А., Осипов Г.С. Введение в прикладную семиотику // Новости искусственного интеллекта. 2002. - N0 6. - С. 28-35.

76. Пуанкаре А. Избранные труды. Т. 1. Новые методы небесной механики. М.: Наука. - 1971. - 771 с.

77. Рудин У. Теория функций в единичном шаре из Сп. М.: Мир -1984. - 455 с.

78. Рябин М., Скотт Д. Конечные автоматы и проблемы их разрешения / Кибернетический сборник. Вып. 4. 1962. - С. 58-91.

79. Самойленко Л.Г. Об одном классе грамматик непосредственно составляющих / Кибернетика. Вып. 2. 1968. - С. 102-103.

80. Сафонов К.В. О множестве точек сходимости двойного степенного ряда // Известия вузов. Матем. 1982. - N0 6. - С. 48-52.

81. Сафонов К.В., Цих А.К. Об особенностях параметрического вычета Гротендика и диагонали двойного степенного ряда // Известия вузов. Матем. 1984. - No 4. - С. 51-58.

82. Сафонов К.В. Об особенностях двумерной композиции Адамара (Аннотацитя статьи) // Сиб. матем. журнал. 1985. - No 4. - С. 200.

83. Сафонов К.В. О условиях алгебраичности и рациональности суммы степенного ряда // Матем. заметки. 1987. - Т. 41. Вып. 3. -С. 325-332.

84. Safonov K.V. Holomorphic extension of two-dimensional Hadamard Product // Selecta Mathematica Soviética. 1989. - V. 8. No 1. -P. 23-30.

85. Сафонов К.В. Монодромия композиции Адамара рациональных функций / Вопросы математического анализа: сборник научных трудов. 1992. - Красноярск. - С. 63-67.

86. Сафонов К.В. О кратных степенных рядах неявнях и мероморф-ных функций многих переменных / Вопросы математического анализа: сборник научных трудов. — 1995. Красноярск. - С. 93-105.

87. Сафонов К.В. Степенные ряды неявных и мероморфных функций многих переменных / Математические модели и методы их исследования: труды международной конференции. 1997. - Красноярск. - С. 162-163.

88. Сафонов K.B. О порядках алгебраичности аналитических функций / Материалы Третьего Сибирского конгресса по прикладной и индустриальной математике. 1998. - Новосибирск. - С. 92-93.

89. Сафонов К.В. О кратных степенных рядах алгебраических и рациональных языков / 5-й Международный семинар-совещание "Кубатурные формулы и их приложения". 1999. - Красноярск.- С. 33-34.

90. Сафонов К.В. О кратных степенных рядах алгебраических и рациональных языков / Труды Международной конф. "Комплексный анализ и дифференциальные операторы" (К 150-летию C.B. Ковалевской). 2000. - Красноярск. - С. 127-133.

91. Safonov K.V. On power series of algebraic and rational functions in Cn // Journal of Math. Analysis and Applications. 2000. - V. 243.- P. 261-277.

92. Сафонов K.B. Ряды Тейлора алгебраических функций как диагонали рядов Лорана рациональных функций / Многомерный комплексный анализ: сборник научных трудов. 2002. - Красноярск.- С. 158-164.

93. Сафонов К.В. О распознавании контекстно-свободных грамматик // Вестник Томского государственного университета. Серия " Математика. Информатика. Кибернетика". 2003. - Прил. No 6. -С. 16-18.

94. Сафонов К.В. О представлении решений произвольных алгебраических уравнений рядами Лорана / Вопросы математического анализа: сборник научных трудов. 2004. - Красноярск. - С. 129— 132.

95. Сафонов К.В. Контекстно-свободные языки как диагонали линейных языков // Вестник Красноярского государственного технического университета. 2004. - Вып. 33. - Красноясрк. - С. 37-41.

96. Сафонов К.В. Проблемы синтаксического анализа и распознавания контекстно-своодных языков / Вопросы математического анализа: сборник научных трудов. 2005. - Красноярск. - С. 143155.

97. Сафонов К.В. Обобщение критерия Кронекера о рациональности суммы степенного ряда на алгебраические функции и его применение // Вестник Красноярского государственного университета. Серия "Физико-математические науки". 2005. - N0 1. - С. - 7680.

98. Сафонов К.В. Распознавание афинных контекстно-свободных языков // Вестник Томского государственного университета. Серия "Математика. Информатика. Кибернетика". 2005. - Прил. N0 14. - С. 26-30.

99. Сафонов К.В. О возможности вычислительного распознавания контекстно-свободных языков // Вычислительные технологии. -2005. Т. 10. N0 4. - С. 91-98.

100. Сафонов К.В. О синтаксическом анализе и свойствах формальных языков программирования // Вычислительные технологии.- 2005. Т. 10. Специальный выпуск. - С. 9-15.

101. Сафонов К.В. Аналитический подход в теории формальных языков программирования / Оптимизация, управление, интеллект: материалы всероссийской конференции "Математика, информатика, управление". Ч. 2. — Иркутск. 2005. - С. 228-232.

102. Семёнов А.Л. Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик // Доклады АН СССР. 1973.- Т. 212. С. 50-52.

103. Спеньер Э. Алгебраическая топология. М.: Мир. - 1971. - 680 с.

104. Стоцкий Э.Д. О некоторых ограничениях на способ вывода непосредственно составляющих / ИТИ. Серия 2. Вып. 7. - 1967. -С. 35-38.

105. Стоцкий Э.Д. Порождающие грамматики и управление выводом / ИТИ. Серия 2. Вып. 10. - 1968. - С. 28-31.I

106. Стоцкий Э.Д. Понятие индекса в обобщенных -грамматиках / ИТИ. Серия 2. Вып. 4. - 1969. - С. 45-48.

107. Умемура X. Решение алгебраических уравнений с помощью тета-констант / Д. Мамфорд. Лекции о тета-функциях. М.: Мир. -1988. - С. 362-370.

108. Фам Ф. Введение в топологическое исследование особенностей Ландау. М.: Мир. - 1967. - 184 с.

109. Фитиалов С.Я. Об эквивалентности грамматик НС и грамматик зависимостей / Проблемы структурной лингвистики. М.: Наука.- 1968. С. 71-102.

110. Харви Р. Голоморфные цепи и их границы. М.: Мир. - 1979. -160 с.

111. Хованский А.Г. Многогранники Ньютона. Разрешение особенностей / Современные проблемы математики. Т. 22. М.: ВИНИТИ.- 1983. С. 207-239.

112. Херц М.М. Энтропия языков, порождаемая автоматной или контекстно-свободной грамматиками с однозначным выводом / ИТИ. Серия 2. Вып. 4. - 1969. - С.89-92.

113. Хомский Н. Синтаксические структуры / Новое в лингвистике.- Вып. 2. М.: Прогресс. С. 412-527.

114. Хомский Н. Три модели для описания языка / Кибернетический сборник: сб. перев. статей / М.: ИЛ. 1961. - Вып. 2. - С. 237-266.

115. Хомский Н. О некоторых формальных свойствах грамматик / Кибернетический сборник: сб. перев. статей / М.: ИЛ. 1962. - Вып. 5. - С. 279-311.

116. Хомский Н. Заметка о грамматиках непосредственно составляющих / Кибернетический сборник. Нов. серия. Вып. 5. М.: Мир.- 1962. С. 312-316.

117. Хомский Н. Логические основы лингвистической теории. — Биробиджан: ИП Тривиум. 2000. - 146 с.

118. Хомский Н., Шютценберже М.Н. Алгебраическая теория контекстно-свободных языков / Кибернетический сборник. Нов. серия. Вып. 3. - М.: Мир. - 1966. - С. 195-242.

119. Хомский Н., Щютценберже М.П. Алгебраическая теория контекстно-свободных языков / Кибернетический сборник. Нов. серия. Вып. 2. - М.: Мир. - 1966. - С. 121-230.

120. Хопкрофт Дж.Э., Мортвани Р., Ульман Дж.Д. Введение в теорию автоматов, языков и вычислений. М.: Вильяме. - 2002. - 528 с.

121. Цих А.К. Критерии представимости интегралов по циклам локальными вычетами. Некоторые применения // Доклады АН СССР. 1984. - Т. 277. N0 5. - С. 1083-1085.

122. Чирка Е.М. Комплексные аналитические множества. М.: Наука.- 1985. 272 с.

123. Шабат Б.В. Введение в комплексный анализ. Ч. 2. М.: Наука. -1976. - 400 с.

124. Шейнов В.П. Критерий рациональности голоморфных функций двух комплексных переменных // Учен, записки МОПИ. 1966.- Т. 166. Вып. 10. с. 223-227.

125. Шрейдер Ю.А. Характеристики сложности структуры текста / ИТИ. Вып. 7. - 1996. - С. 34-39.

126. Южаков А.П. О применении кратного логарифмического вычета для разложения неявных функций в степенные ряды // Математический сборник. 1975. - Т. 97. No 2. - С. 177-192.

127. Южаков А.П., Цих А.К. О кратности нуля ситемы голоморфных функций // иб. матем. журн. 1978. - Т. 19. No 3. - С. 693-697.

128. Янушаускас А.И. Аналитические и гармонические функции многих переменных. Новосибирск: Наука. - 1983. - 183 с. '

129. Янушаускас А.И. Двойные ряды. Новосибирск: Наука. - 1990. -224 с.

130. Baker G.A. Approximate analitic continuation beyond the first Riemann sheet // Lect. Notes. Math. -1984. No 1105. - P. 285-294.

131. Bednarek A.R., Wallace A.D. A relation theoretic result with applications in topological algebra. Mathemetical System Theory.- 1. 1967. - No 3. - P. 12-34.

132. Deligne P. Integration sur une cycle evanescent // Invent. Math. -1984. No 1. - P. 129-143.

133. Djokovic D.Z. A property of the Taylor expansion of a class or rational function in several variables //J. of Math. Analysis and Appl. 1978.- V. 202. P. 34-40.

134. Falb L. Infinite-dimentional filtering // Information and Control. -V. 66. No 2. 1967. - P. 754-759.

135. Ficher P. Turing machines with a schedule to keep // Information and Control. V. 66. No 1. - P. 679-685.

136. Frechet M. Sur la limitation des consequences a tirer de l'évanouissement d'un wronskien // Bull. Math. 1936. - V. 3. -P. 105-109.

137. Gessel I.M. A factorization for formal Lourent series and lattice enumeration. J. Comb. Theory. - 1980. - A28. - P. 32-37.

138. Gilbert R.P., Howard H.C. Singularités of analitic function having integral representation, with remark about elastic //J. Math. Phys.- 1965.-No 7.-P. 1157-1162.

139. Give'on Y. On some properties of the free monoids with applications to automata theory. J. of Computer and System Sciences. -1977. -No 2. - P. 65-70.

140. Graham R. Subsemigroups of 0-simple semigroups // Mathemetical System Theory. 1967. - 3. - P. 41-47.

141. Griffiths P.A. On the periods of certain integrals. // Ann. Math. -1969. V. 90. No 3. - P. 460-495.

142. Hartmanis J. and Davis W.A. Homomorphic images of linear machines // J. of Computer and System Sciences. 1967. - 2. -P. 89-97.

143. Heller A. Stohastic transformations and automata. Mathemetical System Theory. - 1967. - No 3. - P. 68-73.

144. Horn G.M. Lexical-functional grammar. B.: Mouton. - 1983. - 238 P

145. Hibbard N., Gray J. and Harrison M. Scan limited automata and context limited limited grammars // Information and Control. 1969. -V. 11. No 1. - P. 5-14.

146. Mellin H.J. Resolutin de l'equation algebrique generale a l'aide de la fonction // C. R. Acad.Sc. V. 172. - 1921. - P. 658-661.

147. Nilsson N. Some growth and ramification properties of certain integrals on algebraic manifolds // Arkiv for Mathematic. Bd. 5. -Nr. 32. - 1963. - P. 463-476.

148. Rosenberg A.L. A machine realization of the linear context-free languages // Information and Control. 1977. - 10. - P. 175-188.

149. Rosenkrants D. Matrix equations and normal forms for context-free grammars //J. Assoc. Computing Machinery. 14. - 1967. - P. 501-507.

150. Salomaa A., Soittola M. Automata-Theoretics Aspects of Formal Power Series. N.Y.: Springer-Verlag. - 1978. - 288 p.

151. Samelson K, Bauer F.L. Sequential formula translation 11 Commun, of Algebra. 1985. - V. 21. - P. 45-50.

152. Scheinberg S. On property of context-free languages // Information and Control. 1960. - No 3. - P. 372-375.

153. Schorre D.V. A necessary and sufficient condition for a context-free grammar to be unambiguos / System Development Corporation Rept. SP-2153. - July 28. - 1965. - P. 154-156.

154. Schutzenberger M.P. Some remarks on Chomsky's context-free languages // M.L.T. Res. Lab. Electron Quart. Prog. Rept. 1961.- 23-56.

155. Schutzenberger M.P. Context-free languages and pushdown automata // Information and Control. 6. - 1963. - P. 246-264.

156. Schutzenberger M.P. Classification of Chomsky's languages // Proc. IFIP / Working Conference on Formal Language Description Languages. Baden. - 1964. - P. 76-79.

157. Shamir E. A remerk on discovery algorithms for grammars // Information and Control. 1962. - V. 5. - P. 246-251.

158. Shamir E. Mathematical models of languages // Procedings of IFIP Congress. Washington: Spartan Books. - 1965. - P. 17-75.

159. Shamir E.A. A presentation theorem for algebraic and context-free power series in non-commuting variables // Information and Control.- 1967. No 11. - P. 65-78.

160. Srivastava H.M., Karlson P.W. Multiple gausdsian Hypergeometric Series. New York: John Wilery. - 1985. - 252 p.

161. Soitola M. Positive rational sequences // Theoretical Computer Science. 1976. - V. 2. - P. 313-321.

162. Stearns R.E., Hartmanis J. Regularity preserving modifications of regular expressions // Information and Control. 1962. - V. 5. - P. 246-251.

163. Thatcher J.W. Characterizing derivation trees of context-free grammars through a generalization of finite automa ta theory //J. Computer and System Sciences. 1968. - No 1. - P. 132-138.

164. Ullman J.S. Failure of a conjecture about context-free languages // // Journal of Computer and System Sciences. 1967. - No 2. - P. 89-93.

165. Ullman J.D. Pushdown automata with bounded back-track / System Development Corp. Rept. 1966. - V. 9. - P. 61-65.

166. Ullman J.S. Partial algorithm problems for context-free languages // Information and Control. 1967. - V. 11. - P. 80-101.

167. Yntema M.K. Inclusion relations among families of context-free lamguages // Information and Control. 1967. - V. 10. - P. 572-597.

168. Younger D.H. Recognition and parsing of context-free languages in time n3 // Information and Control. 1967. - V. 10. - P. 598-605.