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

На правах рукописи

АЛЕКСЕЕВА Анна Геннадьевна

ПРИМЕНЕНИЕ ИТЕРАЦИИ КОНЕЧНЫХ ЯЗЫКОВ В АЛГОРИТМИЧЕСКИХ ЗАДАЧАХ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ

05.13.18 - математическое моделирование, численные методы и комплексы программ

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

1 7 МАЯ 2012

Тольятти - 2012

005043696

005043696

Работа выполнена в ФГБОУ ВПО <Тольяттинский государственный университет»

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

профессор Мельников Борис Феликсович (Тольяттинский государственный университет)

Официальные оппоненты: доктор технических наук,

профессор Скобцов Юрий Александрович (Украина, Донецкий национальный технический университет)

кандидат физико-математических наук, доцент Кондратьев Алексей Евгеньевич (Ульяновский государственный университет)

Ведущая организация: Ульяновский государственный технический университет

Защита диссертации состоится 30 мая 2012 г. в 13:00 часов на заседании диссертационного совета Д 212.264.03 Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14.

С диссертацией можно ознакомиться в библиотеке Тольяттинского государственного университета, с авторефератом - на сайте диссертационного совета http://edu.tltsu.ru/sites/site.php?s=1496.

Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, Тольятти, ул. Белорусская, 14, диссертационный совет Д 212.264.03.

Автореферат разослан апреля 2012 г.

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

диссертационного совета Д212.081.24, кандидат педагогических наук, доцент

Пивнева C.B.

1 Общая характеристика работы

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

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

Используемые термины «класс» и «подкласс» (вместо «множество» и «подмножество») в различных областях математики часто употребляется для того, чтобы подчеркнуть, что рассматриваемое множество обладает некоторыми специальными свойствами4. В теории формальных языков таким (единственным) свойством часто считается свойство замкнутости рассматриваемого множества языков относительно любых морфизмов5. Если потребовать ещё и замкнутость относительно инверсных морфизмов и пересечений с регулярными множествами, то данный класс языков можно назвать полным абстрактным семейством языков6. Такими свойствами большинство языков, рассматриваемых в данной диссертации, обладают.

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

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

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

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

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

6 Для морфизмов и инверсных морфизмов мы используем терминологию из книги: А.Саломаа: Жемчужины теории формальных языков. - М.: Мир, 1986.

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

7 При этом отметим, что строгого определение понятия «грамматическая структура», приемлемого для всех возможных практических (в том числе - программистских) приложений, вероятно, привести невозможно - однако это понятие нередко употребляется в научной литературе. По-видимому, в большинстве случаев можно пользоваться таким упрощенным определением: «собственное подмноокество правил контекстно-свободной грамматики с возмоо/сным добавлением правил вида А —> и, определяющее непустой язык». См., например: В.Игнатов: Об одном методе построения ЬР(1)-анализатора. - Вестник Моск. ун-та. Сер. 15, 1987, № 1, с.55-61.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объём диссертации. Общий объём диссертационной работы - 123 страницы. Диссертация состоит из введения, 3 глав и заключения, списка используемой литературы из 93 наименований и одного приложения, включающего описание реализованной программы.

2 Содержание работы

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

Введение

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

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

i>0

Для слова и = aja2... а„ будем полагать ил = а„ ...0201- Аналогично для языков: LR = {uR\ueL}.

Далее, пусть заданы 2 алфавита, Д и Е, а также некоторая функция

h : Д - Е*

(т.е. каждой букве а е Д соответствует слово h(a) € Е*). Морфизмом (обозначаемым с помощью того же символа h) называется функция

h : Д* -» £*,

такая что для каждого слова

и = Oí... ап € Д*

имеем

h{u) = /i(ai)... ft(on) •

Обратная функция

/Г1 : Е* 7>(Д*),

определёная на подмножестве множества £*, называется инверсным морфизмом. Отметим, что поскольку морфизм - не обязательно инъективная функция, значениями

10 См. их в монографиях А.Саломаа, а также А.Ахо и Дж.Ульмана. При этом отмстим, что пустое слово будет обозначаться записью е.

инверсного морфизма являются не слова, а множества слов - т.е. языки. (Здесь и далее для произвольного множества А через V(Á] обозначается множество всех подмножеств А.)

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

у. С £* х .

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

{ uSv | (и, v) в f¡} U { w | w е L } .

- для некоторого языка L и множества ¡л. А для определения класса скобочных языков к этому множеству добавляется правило S —» SS. ш-словом называется бесконечная последовательность

а = ai<i2 ... ,

а 2а>словом11 - бесконечная последовательность

/?=... b-ib-ibobib? ...

в других обозначениях - это функции

a:N-»E и 0: Z-»£. При этом слова /3' и /3" считаются равными, если

(Эк 6 Z) (Vi 6 Z) (Р'(г) = 0"(i + к)). Недетерминированный конечный автомат будет обозначаться

K = (Q,Z,6,S,F), (1)

где:

• Q - множество состояний;

• SCQhSCQ - множества стартовых и финальных состояний соответственно;

• 8 : Q х (Е U {е}) —» T(Q) - функция переходов.

Язык автомата (1) будем обозначать записью С(К).

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

_(?>№*) ,-,{£}).

п B.Melníkov: 2w-finite automata and sets of obstructions of their languages. - The Korean Journal of Computational and Applied Mathematics, 1998, V. 6, No. 3, p.565-574.

12 Общая алгебра. Т. 2. - M: Наука, 1991.

13 Используем кальку с английского термина. По-видимому, несколько лучше - «глобальный над-моноид свободного моноида». Однако употребляемый иногда сокращённый термин «надмоноид» здесь ошибочен.

Pref(u) - множество всех префиксов слова и, включая £ и и. Аналогично для языков: Pref (А) = { и | и 6 Pref (и), v 6 А }.

В статье научного руководителя14 рассматривались бесконечные итерации конечных языков. А именно, рассматривались ш-языки вида А", где А - конечный язык над заданным алфавитом Е. (Мы предполагаем, что |Е| > 2 и А $ е.) Для двух конечных языков А в В рассматривалось их равенство Аи = Вы - которое равносильно выполнению специального отношения эквивалентности, также определённого в последней упомянутой статье: А* =оо В' тогда и только тогда, когда одновременно

(Vu 6 А*) (Зи б В') [и е Pref (и))

(2)

(Vt> е В*) (Б и € А') (V е Pref (и)).

Ниже будем писать А = В - вместо обозначения Л* soo В', использовавшегося в предыдущих публикациях.

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

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

В разделе 1.1 приводится алгоритм генерации случайных конечных множеств, для которых выполнено условие (2), - реализованный на основе каких-нибудь (произвольных) алгоритмов случайной генерации:

• слов;

• максимальных префиксных кодов13.

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

Алгоритм 1.

Вход: конечный язык D С Е*.

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

14 B.Melnikov: The equality condition for infinite catenations of two sets of finite words. - International Journal of Foundations of Computer Sciences, 1993, V. 4, No. 3, p.267-274.

15Ж.Лаллемап: Полугруппы и комбинаторные приложения. - М.: Мир, 1985. Несколько различных версий последней генерации приведены далее, в разделе 1.3.

Выход: случайные языки А и В, для которых выполнено условие As В. Описание алгоритма.

Шаг 1. Рассматриваем некоторый новый конечный алфавит Д, такой что |Д| = ¡D¡, и некоторые случайно сгенерированные максимальные префиксные коды Ад и Вд над этим алфавитом. При этом будем писать Ад, Вд 6 тр (Д). Шаг 2. Добавляем некоторые случайные слова к языкам Ад и Вд. Для Лд при этом достаточно рассматривать только такие слова и, для которых и £ Pref (А); аналогично для Вд. Будем писать Лд,Вд £ шр+ (Д).

Шаг 3. Для морфизма h : Д* —> £*, такого что h{Д) = { h{c) \ с £ Д } = D, строим языки Л = /¡(Ад) и В = Л(Вд). При этом будем писать А, В € гар+ (D). Конец описания алгоритма.

Введённые в описании алгоритма обозначения использовались в предыдущих публикациях соискателя и научного руководителя (в частности, в публикации [2]); эти же обозначения будут использоваться ниже. Итак, для языков, которые могут быть получены согласно алгоритма 1, выполнено условие Л, В £ тр+ (£>). Рассмотрим примеры к каждому из 3 шагов алгоритма.

1. Условие Ад = Вд выполнено - поскольку = В% = Д1".

В качестве примера рассмотрим алфавит Д = { 0,1} и два таких языка: Ад = { 0,10,11 } и ЯА = { 00,01,1}.

2. Условие Ад з Вд тоже выполняется. Заметим, что полученные языки, вообще говоря, не являются префиксными.

В качестве продолжения предыдущего примера рассмотрим языки Ад = { 0,10,11,1101 } и Вд = { 00,01,1,111,1110}.

3. Заметим, что язык D = Л(Д) = { Л(с) | с £ Д } тоже, вообще говоря, не является префиксным. Для полученных языков А = Л(Ад) и В = Л(Вд) условие As В также выполняется.

Продолжим рассматривать предыдущий пример. Для (непрефиксного) морфизма h(0) = ab, h( 1) = aba мы получаем следующие языки:

А = { ob, aba ab, aba aba, aba aba ab aba } и В — {abab, ababa, aba, aba aba aba, aba aba aba ab}

В работе доказано следующее достаточное условие:

Утверждение 1 Если для заданных конечных языков А и В и некоторого конечного языка D выполнено условие А, В £ тр* (В),16 то As В.

В разделе 1.2 приводится формулировка необходимого условия равенства бесконечных итераций двух конечных языков. Формулировку этой теоремы можно рассматривать как следствие материала раздела 1.1 и теоремы, доказанной ранее научным руководителем17.

16 Т.е. если языки А и В получены способом, описываемом согласно алгоритму 1 для одного и того же морфизма h : Л" —» причём D — h(Д).

17 См. Theorem 1 в процитированной выше статье в журнале Int. J. of Found, of Сотр. Sci.

Теорема 1 Сформулированное в предыдущем разделе достаточное условие является необходимым и достаточным.

То есть каждая пара конечных языков А и В, для которых выполнено условие А = В, может быть сконструирована с помощью алгоритма, описанного в предыдущем разделе. Иными словами это утверждение для рассматриваемых языков An В (таких что As В) может быть переформулировано следующим образом. Существует конечный язык D (пусть D — { ui,..., ип }), для которого выполняется следующее условие. Для некоторого нового алфавита Д = { ci,..., сп } существуют (конечные) языки А', В' С Д*, такие что:

• А' к В' содержат (вообще говоря, различные) максимальные префиксные коды над Д;

• для морфизма

h:A'-*V, где ft(ci) = щ , ..., h(Cr,) = ип,

выполнены условия h(A') — А и h(B') — В.

Этот язык D (для некоторого рассматриваемого нами языка А) будем далее называть ■«минимальным».

В разделе 1.3 приводится формулировка двух алгоритмов генерации языков класса mp+ (D). Как было отмечено выше, в данной работе приводится подход, необходимый для практического применения результатов в некоторых вспомогательных алгоритмах, предназначенных, в частности, для систем автоматизации построения компиляторов. При этом для разработки, реализации и практической проверки алгоритмов построения «минимального» языка D (по заданному языку А - в предположении А е тр+ (£>)) необходимы алгоритмы генерации соответствующих исходных данных18. При такой генерации наиболее важной составляющей является случайная генерация языков тр (А) для некоторого конечного алфавита Д (точнее - подходы к такой генерации) - эти вопросы и рассматриваются в данном разделе.

Алгоритм 2.

Вход: (положительное) число шагов п. Выход: случайный язык D 6 тр (Д).

18 На связанные темы - о генерации дискретных структур и проверке некоторых свойств такой генерации - см., например:

• статью М. Almeida, N. Moreira, R. Reis: Enumeration and Generation of Initially Connected Deterministic Finite Automata. - Technical Report DCC-2006-07, Univcrsidadc do Porto, December 2006;

• монографию R.Downey, D. Hirschfeldt: Algorithmic Randomness and Complexity. - Springer, ХХУШ, 2010;

• а также следующую диссертацию: О. Рогова: Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов. - Дисс____канд. физ.-мат. паук: 05.13.18, Тольяттинский государственный университет,

Д212.264.03, защищена 13.04.2012.

(Однако подробное обсуждение такой свЯзи выходит за рамки настоящей диссертации.)

Описание алгоритма.

Шаг 1. i:=0; ß:={0 };

Шаг 2. Случайно выбираем слово и € D.19

Шаг 3. D: = Du{uA} \{u}.

Шаг 4■ i:=i+l; если i<n то переход на шаг 2;

Конец описания алгоритма.

Алгоритм 3.

Вход: (положительные) числа m (минимальная длина слова кода) и п (максимальная длина слова кода), такие что ш<п.20 Выход: случайный язык D 6 тр (Д). Описание алгоритма.

Шаг 1. = $ ; F:={ и 6 S* | |u| > т, [u| < п }; (F - некоторый изменяемый вспомогательный язык).

Вспомогательный алгоритм. Операцией D : + и для некоторого слова и € F будем обозначать выполнение следующих действий: D : = D U {и}; F : = F\ {v\u€ Pref(v) или г; € Pref(u)};

Шаг 2. Для некоторого и € F, такого что ]и| = т, выполнить D :+ и; Шаг 3. Для некоторого и G F, такого что jt¿| = п, выполнить D : + u; Шаг 4- если F = ф , то выход из алгоритма Шаг 5. Для некоторого и £ F выполнить D : +и; переход на шаг 4; Конец описания алгоритма.

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

В разделе 1.4 рассматривается связь итераций конечных языков с недетерминированными конечными автоматами. При этом рассматривается алгоритм сведёния рассмотренной выше проблемы равенства cj-языков вида А" к специальной модели, построенной на основе недетерминированных конечных автоматов22.

А именно, для языка А = {t¿i,...,i¿n}, где u¡ = ait\...aUi для i = 1,...,п, рассмотрим недетерминированный конечный автомат

£(Л) = (С?,ЕЛМ,<Э), где Q = {s}U U

<<n, 3<li

со следующей функцией переходов 6 (мы рассматриваем приведённые далее опреде-

19 В настоящее время реализован алгоритм выбора слова согласно дискретному равномерному распределению..

20 Для упрощения описания алгоритма считаем, что п > 2.

21 Как и в алгоритме 2, выбор слова и е F реализован согласно дискретному равномерному распределению..

22 Автоматы и связанные с ними объекты определяются согласно статье: B.Melnikov: Once more on the edge-minimization of nondeterministic finite autómata and the connected problems. - Fundamenta bformaticae, 2010, V.104, No.3, p.267-283. В частности - определенные согласно той статье канонические конечные автоматы, а также функции разметки состояний ip"' и <р°" .

Отметим ещё, что альтернативный алгоритм для проверки равенства (2) был рассмотрен в следующей статье: В.Мельников: Алгоритм проверки равенства бесконечных итераций конечных языков. - Вестник Моск. ун-та. Сер. 15, 1996, №4, с.25-28.

ления для каждого i = 1,..., п). Если |uí| = 1, то 6(s, o¡, 1) Э s; иначе

Э <7¡,i, %А-ь<Ч1() = М и 6{qij-i, üíj) = {g¿,j} для каждого возможного j < ¿¡ - 1.

Очевидно, что такой автомат определяет язык Pref (А*); поэтому условие (2) можно проверить, ответив на вопрос об эквивалентности автоматов К{А) и К.(В).

Для ответа на этот вопрос мы можем использовать канонические автоматы, эквивалентные К{А) и К{В). При этом каждое состояние соответствующего канонического автомата соответствует некоторому подмножеству множества состояний рассматриваемого автомата - например, автомата !С(А).

Такое соответствие также может быть построено на основе функций разметки состояний23. Фактически им является функция (срm)_1. Это соответствие означает следующее. Для некоторого сотсояния q канонического автомата и некоторого слова v входного языка этого состояния (т.е. Cm(q)) существуют некоторые состояния 9х,...,qm автомата )С(А), такие что

v 6 ¿'"Ы_____г/ € £in(?m).

Поэтому если для некоторого («минимального») языка D и некоторого слова v $ D* выполнено условие D = D U {и}, то

q^s для г = 1.....т; атакже \J Ccut{qi) 2 Pref(D').

i<m

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

В разделе 2.1 доказывается, что (конечные) итерации (конечных либо бесконет-ных) языков являются полными абстрактными семействами языков24. Доказательство делится на следующие утверждения - в которых всюду, не ограничивая содержательную часть, предполагаем А ф ф и А ф {г}. При этом допускаем вариант бесконечного языка А; заранее отметим, что в некоторых случаях язык А считается регулярным.

Утверждение 2 Множество языков вида А* замкнуто относительно морфизмов.

Утверждение 3 Множество языков вида А' замкнуто относительно итерации.

Утверждение 4 Множество языков вида А* замкнуто относительно инверсных морфизмов.

Отметим, что утверждение 2 несложное, утверждение 3 тривиальное (оно следует из определений), а утверждение 4 - более сложное, поскольку для любого морфизма h : А* £* обратная функция (т.е. инверсный морфизм /Г1) является, вообще говоря, многозначной.

Из утверждений 2-4 следует

23 См. процитированную выше статью в журнале Fundamenta Informaticac.

24 Определение см. выше.

Теорема 2 Множество языков вида А* является полным абстрактным семейством языков.

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

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

Определение 1 Если язык L обладает следующим свойством:

(Эк е N) (Vu € L) (Н < к) ,

то он называется ограниченным.

Утверждение 5 Если АиВ - ограниченные языки, то АВ - также ограниченный ■ язык.

Утверждение 6 Если АиВ- префиксные языки, то АВ - также префиксный язык. Аналогично, если АиВ- суффиксные языки, то АВ - также суффиксный язык.

Определение 2 Если язык L обладает следующим свойством:

(Va е Е") (Зи е L) (и 6 Pref (а)) ,

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

(Va е Е") (3« е L) (иЙ 6 Pref (а)) , то он называется суффиксно-полным.

Утверждение 7 Если АиВ- полные языка, то АВ - также полный язык. Аналогично, если АиВ - суффиксно-полные языки, то АВ - также суффиксно-полный язык.

Далее для некоторого заданного языка ¿СЕ* будем рассматривать 27 следующие w-языки lim(L) и adh(L);

lim(L) = { а 6 Е" | (VJfc 6 N) (Зи 6 L) (|и| > к, и £ Pref (а)) } , adh (L) = { а 6 Е" | (Vw £ Pref (а)) (Эх е Е") (wx € L) } .

25 Раздел 2.2 является обобщением разделов 3-5 следующей статьи научного руководителя: Б.Мельников: Описание специальных подмоноидов глобального надмоноида свободного моноида. - Изб. вузов. Математика, 2004, №3, c.4G-56.

56 Другими словами: (Va е Е") (£П Pref {a) £ 0).

27 Все связанные с ы-языками обозначения приведены согласно следующим источникам: • S.Eilenberg. Automata, languages and machines. Vol.A. - N.Y.: Acadcmic Press, 1974.

Несложно показывается, что

lim(L) С adh (L),

но, вообще говоря,

lim(L)^adh(L) :

простейшим примером к последнему неравенству является язык L, задаваемый регулярным выражением а'Ь - для него

lim(L) = 0 , a adh (L) = {аш}.

Отметим ещё, что для w-языков lim(L) и adh (L) имеются альтернативные обозначения. Например, иногда вместо lim(L) используются обозначения L и Ls.

Определение 3 Если язык L обладает следующим свойством:

(Уае 2й) ((¿П Pre}{а) Ф 0) или (а е adh (L))) , (3)

то он называется предполным. Аналогично, если предполным языком является то L называется суффиксно-предполным.

Как и для полных языков, при |£| = 1 любой непустой язык является предполным.

Утверждение 8 Если А и В - предполные языки, то AB - также предполный язык. Аналогично, если А и В - суффиксно-предполные языки, то AB - также суффиксно-предполный язык.

Теорема 3 Любой из 72 вариантов, получающихся при выполнении (не выполнении) каждого из следующих 5 ограничений:

• рассматриваются только ограниченные языки;

• рассматриваются только префиксные языки;

• рассматриваются только суффиксные языки;

• рассматриваются только полные (предполные) языки;

• рассматриваются только суффиксно-полные (суффиксно-предполные) языки

• K.Culikll, A.Salomaa. On infinite words obtained by iterating morphisms. - Theoretical Computer Science, 1982, Vol.19, p.29-38.

• W.Thomas. Automata on infinite objects. In: Handbook of Theoretical Computer Scienco. Vol.B. - Elsevier Sci.Publ., 1990, p.301-348.

• L.Staigcr. ¿¿-Languages. In: Handbook of Formal Languages. Vol.3. - Berlin: Springer, 1997, p.339-387.

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

описывает множество элементов супермоноида (множество языков), которое является подмоноидом. Оно образует моноид с операцией конкатенации и единицей

М-

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

Утверждение 9 Любой ограниченный предполный (а также любой ограниченный суффиксно-предполный) язык является полным.

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

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

Материал раздела 2.3 опубликован в [2]; дополнительно в диссертации приведены доказательства некоторых вспомогательных фактов. Мы рассматриваем здесь случай, когда исходные (итерируемые) языки, выше обычно обозначавшиеся А и В, могут содержать бесконечное число слов; в данном разделе мы будем их обозначать А и В.

Определение 4 В данном разделе для языка А и некоторого г > 0 записью -4; будем обозначать подмножество языка А, состоящее из всех его слов длины г:

А = { и £ А | |и| = г} .

Определение 5 Определим линейный порядок У (для произвольных языков над ко- ■ нечными и бесконечными алфавитами).

• Пусть алфавит £ конечный. Будем писать А>- В, если существует некоторое п, для которого выполняются следующие условия:

ИИ = |Л2| = \Вг\, .. ■, IAi.il = 15^1, 1А.1 > \Вп\.

• Пусть алфавит £ бесконечный. Будем писать А У- В, если существует некоторое п, для которого выполняются следующие условия:

Аг = или (А\ 01 и В1<£ А), Аг - Вг или (Аг В2 и В2 £ Аг),

Ап-1 = Вп-1 или (А.-1 <£ Вп-1 и Д.-1 € Ап-\),

Ап э Вп.

Утверждение 11 Если А-В — В- А, то (Уи € В") (Эу 6 А') (и е Рге}{у)).

Дважды применив доказанное утверждение, мы получаем следующую теорему. Теорема 4 Если А ■ В = В ■ А, то А = В.

Глава 3 (Математические модели бесконечных итерируемых языков в задачах теории формальных языков)

В разделе 3.1 приведён пример практического применения итераций бесконечных языков. А именно, они могут быть использованы при описании математических моделей, необходимых для проверки проблемы эквивалентности двух разных описаний языков - в тех подклассах класса контекстно-свободных языков, где такая проверка может быть выполнена28. В тексте диссертации приведены примеры описаний грамматических структур контекстно-свободных языков с помощью т.н. 7г-подклассов29; отметим, что среди этих грамматических структур был и «полный» язык программирования 30 - язык PL/0. Самый важный среди тг-подклассов - а именно, 7г(2)-подкласс

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

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

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

• звёздной высоты конечного автомата (т.е. SH.(K) дня некоторого автомата К)4,

• звёздной высоты состояния конечного автомата (т.е. SH{Kq) для некоторого ■ состояния g автомата А")31.

Точнее, приводятся вспомогательные алгоритмы для описания эвристик определения звёздной высоты недетерминированного конечного автомата, определяющего заданный регулярный язык. Для этого во многих случаях желательно уметь отвечать на

28 Вообще, раздел 3.1 приведён на основе следующей статьи: B.Mclnikov, E.Kashlakova: Some grammatical structures of programming languages as simple bracketed languages. - Informatika (Lithuanian Acad. Sci. Ed.), 2000, V. 11, No. 4, p.441-454. Материал этой статьи писался одновременно со статьёй [2) автора настоящей диссертации (они были опубликованы в одном выпуске журнала)

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

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

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

31 Эти определения согласованы с монографией научного руководителя: Б.Мелышков. Недетерминированные конечные автоматы. - Тольятти: Изд-во ТГУ, 2009.

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

Более формально. Пусть задан недетерминированный конечный автомат (1). Назовём автомат

где32

5' = eF.se 5} и {«о-^о},

простым замыканием автомата (1). Очевидно, что С(К') = (С(К))*, и, кроме того, вЩК*) < БН{К) + 1.

Будем считать, что ни одно из состояний <2 не является ни бесполезным, ни недостижимым. Для некоторого состояния ? 6 <5 рассмотрим автомат

*■, = (<?„ ЕЛ, ш*}),

где ? С <р - состояния, принадлежащие сильно связанной компоненте33, к которой относится состояние q, а <5, совпадает с 8 на элементах С}.

В разделе формулируется и доказывается следующая

Теорема 5 Для выполнения равенства 8Н(К*) — ЗН(К) + 1 достаточно, чтобы для каждого состояния д е такою что ЗН{КЯ) = ЗН(К), было выполнено условие

(<2,п5)и(<2,пР) = 0.

Итак, во всех упомянутых выше задачах нам необходимо ответить на вопрос о том, возможно ли «одинаковое декодирование» двух (конечных либо бесконечных) языков А и В. Эта возможность, согласно материалу 1-й главы, понимается как существование некоторого языка Б, такого что ДВ € тр+ (£)). (Необходимость ответа на вопрос о возможности такого декодирования явно или неявно следует из материала всех предыдущих разделов 1-3 глав.) В разделе 3.3 приведено описание генетического алгоритма, предназначенного для ответа на этот вопрос для некоторых заданных конечных языков А а В. Это делается путём поиска языка О (выше названного «минимальным»), такого что А 6 тр+ (С), и последующим сравнением полученных «минимальных» языков, построенных для заданных языков А и В. Перед описанием генетического алгоритма поиска требуемого языка О доказывается следующая

Теорема 6 Если А £ тр+ (£>), то для любого слова и £ И существует некоторое (зависящее от и) число п, такое что ип € А.

При описании двух следующих алгоритмов мы считаем, что известно некоторое конечное множество слов Р = { «1,..., и„ }. При этом гёном является булевская переменная, обозначающая вхождение некоторого слова множества Р в формируемое множество, особью - массив Ь (размерности п) таких генов, а популяцией - массив особей.

32 В этом разделе мы используем запись функций переходов как множеств.

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

Алгоритм 4.

Вход: конечные языки A, F = { щ,..., и„ } С Е", булевский массив L.

Выход: значение функции приспособленности.

Шаг 1. Сформировать язык G = {u¡ | L[i]=true }.

Шаг 2, Значение функции приспособленности -

I { u е ЛI (3wi,..., vm 6 G)(и = V,... vm)} I - |G|.34

Конец описания алгоритма.

Алгоритм 5.

Вход: конечные языки A, F = { щ,... ,ti„ } С Е", булевский массив L.

Выход: критерий останова.

Шаг 1. Сформировать язык G — { u¡ | L[i] =true }.

Шаг 2. Критерий останова <да» - выполнение следующих двух условий:

А С G' и (Vw 6 G)(A g (G\{w})*).

Конец описания алгоритма.

Алгоритм 6.35

Вход: конечный язык А С Е*, размер популяции, максимально допустимое время работы алгоритма, вероятность применения скрещивания рх. Вспомогательные алгоритмы: функция приспособленности, критерий останова. Выход: приемлемое решение с близким к максимальному значением функции приспособленности; решением является язык G. Описание алгоритма.

Шаг 0. Сформировать язык F = {и | (3v е А)(Эп 6 N)(un = v)}. Шаг 1. Сгенерировать начальную популяцию Ха. При этом каждый ген каждой особи популяции Ха принимает значения true и false с вероятностью Шаг 2. Вычислить приспособленность каждой особи и среднее значение приспособленности для популяции в целом. Посчитать вероятность выбора каждой особи (для пропорционального отбора).36

Шаг 3. Сгенерировать случайное вещественное число из отрезка [0,1]. Если оно превосходит значение рх, то перейти на шаг 5.

Шаг 4■ Путём пропорционального отбора выбрать две особи и произвести операцию скрещивания. Перейти на шаг 6.

Шаг 3. Путём пропорционального отбора выбрать одну особь и произвести операцию мутации.

Шаг 6. Поместить полученную особь в новую популяцию.

Шаг 7. Если новая популяция ещё не сформирована (т.е. не достигнуто необходимое количество особей в ней), то перейти на шаг 3.

Шаг 8. Если не выполнен критерий останова (для лучшей особи популяции) и, кро-

34 При этом среди слов v\,... ,vm возможны повторения.

Отметим ещё, что для более сложного варианта функции приспособленности вычитаемое |G| заменяется на к ■ |G| для некоторой константы к. Однако работа алгоритмов 4-<3 даёт хорошие результаты (см. ниже) и в случае к — 1.

35 Схема генетического алгоритма приводится согласно следующей монографии: J.Hromkovic. Algorithmics for Hard Problems. - Springer, 2003.

36 См. вышеупомянутую монографию Ю.Громковича, а также, например, следующую монографию: Дж.Люгер. Искусственный интеллект: стратегии и методы решения сложных проблем. - Вильяме, 2003.

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

Шаг 9. Сформировать выходной язык G — |L[i] =true } для массива L, относящегося к лучшей особи последней популяции. Конец описания алгоритма.

При выполнении вычислительных экспериментов выбирались следующие значения:

• размер алфавита выбирался от 2 до 16 букв;

• язык D, являющийся входом алгоритма 1, содержал от 10 до 100 слов - при этом максимальная длина слова языка D не превышала 20 и не менее чем у 50% слов языка D нарушалось свойство префикса1;

• параметры алгоритмов 1-3 были подобраны так, чтобы в результате их работы язык А включал от 5000 до 10000 слов;

• размер популяции выбирался равным 25;

• максимально допустимое время работы алгоритма выбиралась равным 1 сек (на компьютере с тактовой частотой 2 ГГц);

• вероятность применения скрещивания рх выбиралась 5.

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

Алгоритм 7.

Вход: конечные языки А, В С £*.

Выход: ответ на вопрос, существует ли язык D, для которого А, В е mp+ (£>). Описание алгоритма.

Шаг 1. Применяем алгоритм 6 к языку А - получаем язык D Шаг 2. Применяем алгоритм 6 к языку В - получаем язык D2. Шаг 3. Выход из алгоритма с ответом «да» в случае D\ — D?.38 Конец описания алгоритма.

Заключение

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

37 J.Hromkovic. Design and Analysis of Randomized Algorithms. - Springer, 2005.

38 Как обычно в рандомизированных алгоритмах, мы в случае Di Ф £>2 заканчиваем работу с ответом «нет», однако при этом мы не можем утверждать с вероятностью 1, что искомого языка D не существует, т.е. что А ф В.

Список используемой литературы

Список литературы включает 111 наименований.

Приложение

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

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

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

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

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

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

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

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

Список литературы

[1] А. Бросалина: Об условиях коммутирования в глобальном надмоноиде свободного моноида. - Ученые записки Ульяновского государственного университета, сер. «Фундаментальные проблемы механики и математики», №2(9), 2000. - С.6-21.

[2] A. Brosalina, B.Melnikov: Commutation in global supermonoid of free monoids. -Informatika (Lithuanian Acad. Sei.Ed.), Vol.11, No. 4 (2000) 401-413. (Рецензируемый журнал, рекомендованный ВАК.)

[3] А. Алексеева, В. Мельников: Итерации конечных и бесконечных языков и недетерминированные конечные автоматы. - Вектор науки Тольяттинского государственного университета, №3(17), 2011. - С.30-32. (Рецензируемый журнал, рекомендованный ВАК.)

[4] А.Бросалина, Б.Мельников: Сведение задач минимизации конечных автоматов к работе с орграфами. - Труды научной конф. «Математическое моделирование физических, технических, социальных систем и процессов», Ульяновск, . 1998. - С.15.

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

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

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

[8] А. Бросалина: Оценка эвристических алгоритмов построения регулярного выражения по конечному автомату. - Материалы II Международной научно-практической конф. «Компьютерные технологии в науке, производстве, социальных и экономических процессах», Новочеркасск, 2001. - 4.1. - С.11.

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

[10] А. Бросалина: Эвристические алгоритмы построения регулярного выражения с минимальной звездной высотой по заданному конечному автомату. - Материалы Международной научно-практической конф. «Методы и алгоритмы прикладной математики в технике, медицине и экономике», Новочеркасск, 2001. -4.5. - С. 50-52.

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

Подписано в печать 26.04.2012. Формат 60x84/16 Печать оперативная. Усл. п.л. 1.5. Тираж 100 экз. Заказ № 3-100-12.

Издательство Тольяттинский государственный университет 445667. г. Тольятти, ул. Белорусская. 14

Введение

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

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

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

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

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.

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

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.