Применение итераций конечных языков в алгоритмических задачах теории формальных языков тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Алексеева, Анна Геннадьевна

• Алексеева, Анна Геннадьевна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Алексеева, Анна Геннадьевна

Введение

Исторический обзор

Общая характеристика диссертации

Структура диссертационной работы

Применяемые обозначения.

1 Итерации языков и конечные автоматы

1.1 Алгоритм генерации специальных морфизмов

1.2 Необходимое условие равенства бесконечных итераций

1.3 Алгоритмы генерации дополненных максимальных префиксных кодов.

1.4 Итерации языков и конечные автоматы.

2 Случай бесконечных итерируемых языков

2.1 Итерации языков как абстрактные семейства

2.2 Подмоноиды супермоноида.

2.3 Эквивалентность для случая бесконечных итерируемых языков.

3 Модели бесконечных итерируемых языков

3.1 Специальное описание грамматических структур КС-языков.

3.2 Итерации языков и проблема звёздной высоты

Оглавление

3.3 Алгоритмы специального декодирования.

Введение диссертации (часть автореферата) на тему «Применение итераций конечных языков в алгоритмических задачах теории формальных языков»

Исторический обзор

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

Для задания класса КС-языков существуют различные формализмы. Кроме обычных контекстно-свободных грамматик ([2, 3] и мн.др.) - которые в некоторых приложениях неудобны тем, что не формулируют явные алгоритмы ответа на вопрос, принадлежит ли некоторое слово заданному языку - упомянем различные расширения класса конечных автоматов. Расширения, наиболее близкие к тематике настоящей диссертации, описанных в монографии А.Оллонгрена [48], а также в серии статей Л.Станевичене - [55, 56, 88] и др. Поэтому во многих приложениях (прежде всего - в системах автоматизации построения компиляторов, [50] и мн.др.) желательны формализмы, являющиеся алгоритмами. Такими формализмами являются, например, «обычные» магазинные автоматы1, а также их различные расширения.

Для некоторых задач во всём классе КС-языков доказана алгоритмическая неразрешимость - в частности для задач провер

1 Или автоматы с магазинной памятью, МП-автоматы. См. [2, 3, 63] и

ДРки однозначности КС-грамматики, эквивалентности двух КС-грамматик, принадлежности языка КС-грамматики классу регулярных языков (проблема регулярности). Этот факт является важным аргументом для рассмотрения собственных подклассов класса контекстно-свободных языков.

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

По-видимому, для всех формализмов, задающих некоторый подкласс класса КС-языков, в частности - для каждого из формализмов, упомянутых выше, самой ваэ/сной из также упомянутых выше алгоритмических задач является получение ответа на вопрос, разрешима ли в этом подклассе проблема эквивалентности. Как известно, в классе регулярных языков проблема эквивалентности разрешима - что проще всего доказывается путём построения двух канонических конечных автоматов, определяющих заданные языки, и последующей проверкой их изоморфизма ([3, 45, 54] и мн.др.). Однако, как уже было отмечено, во всём классе контекстно-свободных языков проблема эквивалентности неразрешима - это проще всего показывается путём применения проблемы соответствий Поста, см. [3, 25, 26, 34, 63]. В связи с этим возникают задачи описания как можно более широких подклассов класса КС-языков с разрешимой проблемой эквивалентности. При этом желательно рассматривать подклассы, с помощью которых - при использовании некоторых упрощений 2 - могут быть описаны реальные языки программирования.

Однако с начала 1970-х годов такая задача (вопрос о существовании подклассов класса КС-языков с разрешимой проблемой эквивалентности и удобном описании этих подклассов) в научных исследованиях была фактически заменена на другую: разрешима ли проблема эквивалентности в одном конкретном подклассе - а именно, в классе детерминированных контекстно-свободных языков. Возможно, это связано с тем, что фактически такой вопрос был поставлен в известной монографии [23] (1966 г. на языке оригинала) - причём очень важно отметить, что он был поставлен ещё до окончательной формулировки описания класса детерминированных КС-языков в терминах грамматик (в монографии [3], изданной на языке оригинала в 1972 г., такое описание уже имеется).

Вопрос о разрешимости проблемы эквивалентности в классе детерминированных контекстно-свободных языков решался около 20 лет. В настоящее время считается, что эта проблема решена Ж.Сьёнизергом (С. Зётге^иез) в конце 1990-х - см. обобщающую работу [87]. Однако это доказательство - чрезвычайно громоздкое и сложное для понимания, на его основе, по-видимому, невозможно создать реально работающие компьютерные программы; это заставляет искать более компактное и естественное решение.

Во многих работах отечественных учёных (в основном -в работах, опубликованных в 1980-х) было приведено решение этой проблемы - либо частичное, либо заявлявшееся как полное. Важные подклассы класса детерминированных КС-языков с разрешимой проблемой эквивалентности были описаны в 1980-м и в 1986-м В. Романовским в [52, 53]; причём важно отметить, что и эти подклассы - при использовании некото

2 Например - при остутствии требования обязательного описания переменной до её использования в программе. Такое требование делает описываемый язык не контекстно-свободным, см. соответствующий пример и его обсуждение в [63]. рых упрощений, аналогичных упомянутым выше, - могут быть использованы для описания реальных языков программирования. Кроме того, автору и научному руководителю неизвестно, чтобы кто-либо обнаружил ошибки в доказательстве, приведённом в серии работ Л.Станевичене - см. вышеупомянутые статьи [55, 56, 88], а также работы, процитированные в них. По-видимому, можно довести до конца и не совсем завершённое доказательство В.Мейтуса, приведённое в [37], - явных ошибок та статья не содержит.

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

• не совпадают с классом детерминированных КС-языков;

• имеют разрешимую проблему эквивалентности;

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

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

Упомянем ещё некоторые задачи, связанные с описанными выше и рассматривавшиеся в научных работах в последние 20 лет. Это, прежде всего, задачи графического описания магазинных автоматов - [20]. Среди многих работ, посвящённых однозначным объектам (языкам, грамматикам и распознавателям), занимающим промежуточное положение между соответствующими детерминированными объектами и объектами без ограничений, упомянем ставшую классической работу [93]; в ней (а также написанных впоследствии, в том числе в работе научного руководителя [42]) рассматриваются классы конечных автоматов. Описание подклассов класса КС-языков связано с проблемой звёздной высоты (определяемой как для конечных автоматов, так и для регулярных языков); кроме публикаций автора данной диссертации (см. также раздел 3.2 ниже) упомянем следующие работы: [6, 57, 84]. Связаны с описанием подклассов класса КС-языков и некоторые специальные алгебраические структуры; среди множества работ по автоматным алгебрам и т.п. объектам, связанным с тематикой диссертации, отметим недавние [21, 32].

Общая характеристика диссертации

Актуальность темы

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

Использованные выше термины «класс» и «подкласс» (вместо «множество» и «подмножество» - см., например, [40]) употребляются в различных областях математики. Они часто применяется для того, чтобы подчеркнуть, что рассматриваемое множество обладает некоторыми специальными свойствами. В теории формальных языков часто таким свойством, причём единственным, считается свойство замкнутости рассматриваемого множества языков относительно любых морфизмов3. (При этом иногда дополнительно требуются свойства замкнутости

3 Для морфизмов мы используем терминологию из книги [54]. При этом отметим, что в различных областях алгебры термином «морфизм» иногда называют и другие (схожие) понятия. Подробное определение, применяемое нами, см. ниже. относительно объединения и итерации - отметим, что последнее свойство в нашем случае также выполнено.)

А если потребовать ещё и замкнутость относительно инверсных морфизмов4 и пересечений с регулярными множествами, то данный класс языков можно назвать полным абстрактным семейством языков ([24, 34, 54]). Такими свойствами большинство языков, рассматриваемых в данной диссертации, обладают.

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

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

Рассмотрим три примера:

• простейший пример - пара простых (например, фигурных) скобок. { и }, например в языке Си;

4 Итерация языков и инверсные морфизмы также определены в вышеупомянутой монографии А.Саломаа. Строгие определения приводятся далее.

• немного более сложный - пара скобок begin и end в языке Паскаль;

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

По-видимому, эти примеры можно считать поясняющими все возможные ситуации.

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

Важно отметить, что подобные конструкции могут появляться и в двухуровневых грамматиках (в частности, при описании языка Алгол-68, [91]) - причём принципиально иным способом, чем рассмотренный в данной диссертации, однако последний формализм может описывать ещё более мощные конструкции и поэтому мало приемлем, например, для описания подклассов класса КС-языков с разрешимой проблемой эквивалентности.

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

Цель работы

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

Основные задачи исследования

Для достижения указанной цели были поставлены следующие задачи.

1. Описание формализма для приемлемого представления бесконечных итераций конечных и некоторых бесконечных языков в прикладных задачах теории формальных языков - в том числе для программного представления этих итераций.

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

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

4. Описание применения бесконечных итераций языков в описании моделей задач, связанных с контекстно-свободными языками; в первую очередь - задач решения проблемы эквивалентности в некоторых подклассах класса КС-языков.

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

Объект исследования

Объектом исследования являлись:

• бесконечные итерации конечных и бесконечных языков;

• построенные на их основе математические модели специальных недетерминированных конечных автоматов;

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

Предмет исследования

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

Методы исследования

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

Результаты исследования

Результатами диссертационного исследования являются новые утверждения и теоремы теории формальных языков, а также новые вычислительные алгоритмы.

Научная новизна

Научная новизна диссертационной работы состоит в следующем.

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

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

• Предложены подходы к алгоритмизации возникающих задач дискретной оптимизации.

Достоверность результатов

Достоверность результатов подтверждается приведёнными в диссертации доказательствами утверждений и теорем.

Практическая значимость исследования

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

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

• На основе приведённых доказательств можно сформулировать необходимые и достаточные условия коммутирования в глобальном надмоноиде (супермоноиде) свободного моноида и его подмоноидах.

• Можно описать связь между рассматриваемыми здесь проблемами со специальными си-языками (языками, состоящими из бесконечных слов, т.е. а>слов) и 2ы-языками, а также определяющими их и- и 2о;-автоматами.

• Задачи, рассматриваемые в настоящей работе, возникают при т.н. графическом описании класса КС-языков и некоторых его подклассов.

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

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

Основные положения, выносимые на защиту

• Алгоритм сведения проверки равенства бесконечных итераций конечных языков к проверке эквивалентности недетерминированных конечных автоматов.

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

• Формулировка свойств итераций языков в терминах алгебры полугрупп.

• Подход к описанию моделей для решения проблемы эквивалентности в некоторых подклассах класса контекстно-свободных языков.

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

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

Апробация работы

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

• Научные семинары кафедр «Прикладная математика» и «Теоретические основы информатики» Ульяновского государственного университета. 1997-2003.

• Научные конференции «Математическое моделирование физических, экономических, социальных систем и процессов», Ульяновск, УлГУ, 1998-2001.

• VII Международный научный семинар «Дискретная математика и её приложения», Москва, МГУ, 2001.

• II Международная научно-практическая конференция «Компьютерные технологии в науке, производстве, социальных и экономических процессах», Новочеркасск, 2001.

• Международная научно-практическая конференция «Методы и алгоритмы прикладной математики в технике, медицине и экономике», Новочеркасск, 2001.

• Научные семинары кафедры «Прикладная математика и информатика» Тольяттинского государственного университета, 2011-2012.

Публикации

Основные результаты диссертации опубликованы в 11 работах, 2 из которых входят в список изданий, рекомендованных ВАК.

Личный вклад

Изложенные утверждения и теоремы доказаны лично автором, либо совместно с научным руководителем.

Структура диссертационной работы

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Алексеева, Анна Геннадьевна

Основные результаты диссертации

1. Разработал алгоритм сведения проверки равенства бесконечных итераций конечных языков к проверке эквивалентности недетерминированных конечных автоматов и доказана его корректность.

2. Доказаны некоторые свойства итераций языков, показывающие, что множество итераций представляет собой абстрактное семейство языков.

3. Сформулированы некоторые свойства итераций языков в терминах алгебры полугрупп.

4. Разработан подход к описанию моделей для решения проблемы эквивалентности языков. На основе разработанного подхода решена эта проблема в некоторых подклассах класса контекстно-свободных языков.

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

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

Заключение

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

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

• На основе условий выполнения отношения А = В можно сформулировать некоторые необходимые и достаточные условия коммутирования в глобальном надмоноиде (супермоноиде) свободного моноида и некоторых его собственных подмоноидах - [44, 74]. Иными словами - сформулировать некоторые критерии для выполнения равенства АВ = В А, где А, В СЕ*.

• Возможная связь между условиями выполнения отношения А = В и некоторыми другими алгебраическими проблемами может быть получена на основе результатов статей научного руководителя [43, 76, 79], в которых рассматриваются и- и 2и;-языки11, порождённые в результате бесконечных последовательностей отражений точки от сторон некоторого многоугольника (иными словами - порождённые специальными биллиардами). Эти результаты связаны с алгоритмическими проблемами для мономиальных алгебр (т.е. ассоциативных алгебр, заданных с помощью т.н. языков обструкций). Такая связь следует из результатов, приведённых в широко известных работах [7, 59] и ДР

• Задачи, рассматриваемые в настоящей статье, возникают при графическом описании класса КС-языков и некоторых его подклассов - см. [20, 55], - в частности, при решении проблем эквивалентности в этих подклассах.12

• Как было отмечено выше, «бесконечный случай» - т.е. когда мы в (2) допускаем возможность бесконечных языков А или В - по-видимому, менее интересен, чем «конечный». Однако всё-таки в некоторых задачах необходимость рассмотрения бесконечных языков Л и В возникает - например, в случае когда рассматривается задача описания условий эквивалентности морфических образов скобочных языков. (См. [30, 40, 66, 82]; отметим, что в этих работах рассматривались и другие варианты применения морфизмов бесконечных языков при описании некоторых подклассов класса КС-языков.)

11 Например, 2ш-словом а над заданным алфавитом Е можно считать любое отображение вида а : —* Е.

12 Более того, развитие этого графического подхода даёт возможность описать - также графически - языки, имеющие в иерархии Хомского типы 1 и 0.

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

Список литературы диссертационного исследования кандидат физико-математических наук Алексеева, Анна Геннадьевна, 2012 год

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

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

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

4. А.Белов, В. Борисенко, В.Латышев: Мономиальные алгебры Итоги науки и техн., сер. Современная математика и её приложения, Тем. обзоры, Т. 26, М., ВИНИТИ, 2002, 35-214.

5. С.Богомолов: О восстановлении автомата по экспериментам Дискретная математика, 1989, № 1, с.135-146.

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

7. А.Бросалина: Одно из свойств глобальных надмоноидов- Труды 2-й научной конф. «Математическое моделирование физических, технических, социальных систем и процессов», Ульяновск, 1999. с.22.

8. А.Бросалина: Обобщение утверждения об условиях коммутирования слов на случай языков в глобальных надмоно-идах Труды 2-й научной конф. «Математическое моделирование физических, технических, социальных систем и процессов», Ульяновск, 1999. - С.23.

9. А.Бросалина: Построение фундаментального множества циклов и его связь с проблемами звездной высоты Труды Международной школы-семинара «Дискретная математика и математическая кибернетика», М.: Макс Пресс, 2001. - с.15.

10. А.Бросалина: Оценка эвристических алгоритмов построения регулярного выражения по конечному автомату Материалы II Международной научно-практической конф.

11. Компьютерные технологии в науке, производстве, социальных и экономических процессах», Новочеркасск, 2001.- 4.1. с.11.

12. А.Бросалина: Функции риска в алгоритмах построения регулярных выражений со звездной высотой, близкой к минимальной Труды научной конф. «Математическое моделирование физических, технических,- социальных систем и процессов», Ульяновск, 2001. - с. 36.

13. А.Бросалина: Эвристические алгоритмы построения регулярного выражения с минимальной звездной высотой по заданному конечному автомату Материалы VII Международного семинара «Дискретная математика и ее приложения», М., 2001. - Ч.З. - С.145-146.

14. А. Вылиток: О построении графа магазинного автомата- Вестник Московского университета, сер. 15, 1996, №3, с. 68-73.

15. А. Гаврюшкина: Ранг Скотта автоматных частичных порядков Вестник НГУ, сер. Математика, механика, информатика, 2010, Т. 10, Вып. 2, с.37-44.

16. А. Гилл : Линейные последователъностные машины. М., Наука, 1974.

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

18. С. Гинзбург, Ш. Грейбах : Абстрактные семейства языков В кн.: Языки и автоматы, М., Мир, 1975.

19. А. Гладкий : Некоторые алгоритмические проблемы для КС-грамматик Алгебра и логика, 1965, Т. 4, № 1, с.3-13.

20. A. Гладкий : Алгоритмическая нераспознаваемость существенной неопределенности КС-языков Алгебра и логика, 1965, Т. 4, №1, с.53-64.

21. И.Грунский: Анализ поведения конечных автоматов. Луганск, 2003

22. И. Грунский, В. Козловский : Синтез и идентификация автоматов. Киев, Наукова думка, 2004. •

23. С. Гудман, С. Хидетниеми : Введение в разработку и анализ алгоритмов. М., Мир, 1981.

24. О.Дубасова, Б.Мельников: Об одном расширении класса контекстно-свободных языков Программирование (РАН), 1995, №6, с.46-58.

25. B.Игнатов: Об одном методе построения ЬР(1)-анализатора Вестник Моск. ун-та. Сер. 15, 1987, №1, с.55-61.

26. C. Илясов : Распознавание некоторых свойств автоматных алгебр Алгебра, СМФН, РУДЕ, 2006, .№20, с.104-147.

27. Н.Иванов, Г.Михайлов, В.Руднев, А. Таль: Конечные автоматы: эквивалентность и поведение. М., Наука, 1984.

28. Ж. Лаллеман : Полугруппы и комбинаторные приложения. М., Мир, 1985.

29. Дж. Люгер : Искусственный интеллект: стратегии и методы решения сложных проблем. М.-СПб-Киев, Вильяме, 2003.

30. Математическая энциклопедия. М., Советская энциклопедия, 1979.37| В. Мейтус : Разрешимость проблемы эквивалентности детерминированных магазинных автоматов Кибернетика и системный анализ, 1992, №5, с.20-45.

31. Б.Мельников: Некоторые следствия условия эквивалентности однозначных скобочных грамматик Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка, 1991, №3, с.51-53.

32. Б. Мельников: Об одной классификации последователь-ностных контекстно-свободных языков и грамматик -Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка, 1993, №3, с.64-69.

33. Б.Мельников: Подклассы класса контекстно-свободных языков. М., Изд-во МГУ, 1995.

34. Б. Мельников: Алгоритм проверки равенства бесконечных итераций конечных языков Вестник Моск. ун-та. Сер. 15, 1996, №4, с.25-28.

35. Б. Мельников : Однозначные конечные автоматы Известия ВУЗов, серия «Технические науки» (Поволжский регион), № 2 (2002).43J Б.Мельников: Об cj-языках специальных биллиардов -Дискретная математика (РАН), Т. 14, № 3 (2002), 95108.

36. Б. Мельников : Описание специальных подмоноидов глобального надмоноида свободного моноида Изв. вузов. Математика, №3 (2004) 46-56.

37. Б.Мельников: Недетерминированные конечные автоматы. Тольятти, Изд-во ТГУ, 2009.

38. Общая алгебра. Т. 1. М., Наука, 1990.

39. Общая алгебра. Т. 2. М., Наука, 1991.

40. А. Оллонгрен : Определение языков программирования интерпретирующими автоматами. М., Мир, 1977.

41. О. Ope: Теория графов. М., Наука, 1980.

42. Т. Пратт, М.Зелковиц: Языки программирования: разработка и реализация. СПб., Питер, 2002.

43. В. Романовский : Проблема эквивалентности для строгих детерминированных МП-автоматов, действующих в реальное время Кибернетика, 1980, №5, с.49-59.

44. В. Романовский : Проблема эквивалентности детерминированных МП-автоматов, действующих в реальное время -Кибернетика, 1986, №2, с.13-23.

45. А.Саломаа: Жемчужины теории формальных языков. М., Мир, 1986.

46. Л. Станевичене : Об одном средстве исследования бесконтекстных языков Кибернетика, 1989, №4, с.135-136.

47. Л. Станевичене: О некоторых определениях класса КС-языков Программирование (РАН), 1999, Ns5, с.15-25.

48. П. Сутырин: О множестве памятей D-графа Вестник Московского университета, сер. 15, 2010, №1, 45-51.

49. В. Трахтенброт, Я. Бардзинь : Конечные автоматы: поведение и синтез. М., Наука, 1970.

50. В. Уфнаровский: Комбинаторные и асимптотические методы в алгебре Итоги науки и техн., сер. Соврем, пробл. матем., Алгебра, Т. 6, М., ВИНИТИ, 1990, 5-177.

51. С.Фитиалов: Формальные грамматики. Изд-во ЛГУ, 1984.

52. Ф.Харари: Теория графов. М., Мир, 1973.

53. Ф.Харари, Э.Палмер: Перечисление графов. М., Мир, 1975.

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

55. С.Яблонский: Введение в дискретную математику. М. Наука, 1986.

56. M.Almeida, N.Moreira, R. Reis: Enumeration and Generation of Initially Connected Deterministic Finite Automata Technical Report DCC-2006-07, Universidade do Porto, December 2006.,

57. A. Brosalina, B.Melnikov: Commutation in global supermonoid of free monoids Informatika (Lithuanian Acad. Sci. Ed.), Vol. 11, No. 4 (2000) 401-413. (Публикация автора в рецензируемом журнале, рекомендованном ВАК.)

58. K.Culik II, A.Salomaa: On infinite words obtained by iterating morphisms Theoretical Computer Science, 1982, Vol.19, 2938.

59. R. Downey, D. Hirschfeldt: Algorithmic Randomness and Complexity. Springer, XXVIII, 2010.

60. S.Eilenberg: Automata, Languages and Machines. Vol. A. N.Y., Academic Press, 1974.

61. J.Hromkovic: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2003.

62. J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer, 2005.

63. B. Melnikov : The equality condition for infinite catenations of two sets of finite words Int. J. of Found, of Сотр. Sci., V. 4, No. 3 (1993) 267-274.

64. B.Melnikov: Some equivalence problems for free monoids and for subclasses of the CF-grammars class World Sci. Publ, 1995, 67-68.

65. B. Melnikov: 2cj-finite automata and sets of obstructions of their languages Journal of Applied Mathematics and Computing (The Korean Journal of Computational and Applied Mathematics), Springer Berlin/Heidelberg, V. 6, No. 3 (1999) 565-574.

66. B. Melnikov: Discrete optimization problems some new heuristic approaches - 8th International Conference on High Performance Computing and Grid in Asia Pacific Region, 2005. - 73-80.

67. B. Melnikov: On an axpansion of nondeterministic finite automata Journal of Applied Mathematics and Computing (The Korean Journal of Computational and Applied Mathematics), Springer Berlin/Heidelberg, V. 24, No. 12 (2007) 155-165.

68. B. Melnikov: Extended nondeterministic finite automata -Fundamenta Informaticae, V. 104, No. 3 (2010) 255-265.

69. B. Melnikov: Once more on the edge-minimization of nondeterministic finite automata and the connected problems Fundamenta Informaticae, V. 104, No. 3 (2010) 267-283.

70. B.Melnikov, Е. Kashlakova: Some grammatical structures of programming languages as simple bracketed languages -Informática (Lithuania), V. 11, No. 4 (2000) 441-454.

71. B. Melnikov, A. Vakhitova: Some more on the finite automata Journal of Applied Mathematics and Computing (The Korean Journal of Computational and Applied Mathematics), Springer Berlin/Heidelberg, V.5, No. 3 (1998) 495-506.

72. D.Perrin: Finite Automata. Handbook of Theoret. Comput. Sci., Vol. A. Elsevier Sci.Publ., 1990.

73. M. Rabin, D. Scott: Finite automata and their decision problems IBM J. Research and Development, Vol. 3 (1959) 114-125. (Имеется русский перевод в кн.: «Кибернетический сборник, вып. 4», М., Иностранная Литература, 1962, 58-91.)

74. G. Sénizergues: L(A)=L(B)? decidability results from complete formal systems Theor. Comput. Sci, Vol.251, No. 1-2 (2001) 1-166.

75. L. Staneviciené: D-graphs in context-free language theory -Informática (Lithuanian Acad. Sci. Ed.), 1997, V. 8, No. 1, 4356.

76. L. Staiger: co-Languages. Handbook of Formal Languages, Vol 3. Springer, Berlin 1997, 339-387.

77. W. Thomas: Automata on Infinite Objects. Handbook of Theoret. Comput. Sci., Vol. B. Elsevier Sci. Publ., 1990.

78. A. van Wijngaarden (ed.): Revised report on the algorithmic language ALGOL 68. Springer, 1976.

79. D.Wood: Grammar and L Forms: an Introduction. Berlin, Springer, 1980.

80. A. Weber, H. Seidl: On the degree of ambiguity of finite automata Theoretical Computer Science, 1991, V. 88, No. 2, 325-349.