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

Зузанова Мария Раф&эльевна

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

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

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

Тольятти - 2009

003487836

Работа выполнена в Тольяттинском государственном университете

Научный руководитель:

доктор физико-математических наук, профессор Мельников Борис Феликсович

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

доцент Лиманова Наталия Игоревна

кандидат физико-математических наук Белозёрова Алла Равильевна

Ведущая организация:

Ульяновский государственный педагогический университет им. И. Н. Ульянова

Защита диссертации состоится 29 декабря 2009 года в 14.30 на заседании диссертационного совета Д 212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14.

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

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

Автореферат разослан » ноября 2009 года

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

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

кандидат педагогических наук Пивнева C.B.

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

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

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

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

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

2. Формулировка и доказательство теорем о корректности этих алгоритмов и свойствах отношения ф.

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

Объект исследования. Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева).

Предмет исследования. Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами.

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

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

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

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

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

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

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

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

3. Доказательство теоремы о том, что для двух конечных автоматов возможна любая таблица отношения в которой нет одинаковых, пустых строк и столбцов, а также если в «меньшем» из двух канонических автоматов имеется N состояний, то в «большем» из них - их не более, чем 2" -I.1

4. Доказательство теоремы о том, что если в таблице отношения # строк и столбцов не более, чем N (каждых), то число блоков2 не более, чем ЛГ2.

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

1Будем говорить, что один детерминированный автомат является «большим» по отношению к другому детерминировавному автомату тогда и только тогда, когда он имеет большее количество состояний, чем другой детерминированный автомат. Тогда другой детерминированный автомат, будем называть «меньшим». Если автоматы имеют равное количество состояний, то любой из них будем называть «большим». Данные понятия используются далее.

Определение блока будет приведено далее.

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

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

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

• XVTII Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2006);

• XXI Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2008);

• семинаре кафедры математического анализа физико-математического факультета ГОУ УлГПУ им. И. Н. Ульянова (г. Ульяновск, 2009).

• Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и зашиты информации» (г. Ульяновск, 2009).3

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

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

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

3 Участие в этой кгафереэда планируется после публикации автореферата, но тезисы

уже приняты к публикации.

2 Краткое содержание работы

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

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

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

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

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

Определение 1 Недетерминированным конечным автоматом называется пятёрка

где:

• Q - некоторое конечное множество, называемое множеством состояний (вершин).

Разработкой алгоритмов, в чём-то аналогичных алгоритмам, сформулированным в виде теорем 1-3 в данной работе, занимаются также и зарубежные авторы. Например, такие алгоритмы можно найти в работе [Hie, L. Reducing the size of NFAs by using equivalences and preorders / L. Ше., R. Solis-Oba, S. Yu - Springer Berlin / Heidelberg, 2005].

6[Hromkovic, J. Algorithmics for Hard problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics / J. Hromkovic. - Springer, 2004] и [Люгер, Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание. / Д.Ф. Люгер. - М. : Вильяме, 2003].

• £ - некоторый алфавит. Автомат К вводится для задания некоторого языка над этим алфавитом.

• 5 — функция переходов вида6

5:Qx(EU{e})->P(Q).

Кроме вышеприведённого стандартного способа задания функции переходов конечных автоматов также будем использовать функцию у вида

7 : Q х Q7>(S U {е}).

Функция 7 задаётся по S следующим образом:

если<5(д,а) Э г,то7(д,г) Э а.

Других значений функция 7 не имеет.

• S С Q ~ множество стартовых состояний (входов)..

• F С Q - множество финальных состояний (выходов). □ Определение 2 Пусть

£=(<?„ ЕЛ, {«„}.£,) и =

являются каноническими автоматами7, которые задают языки L и LR.

Бинарное отношение # (где # С Qw х определяется следующим образом для пары состояний автоматов L и LH:

АфХ если и только если (Эда е Ь) (и € Cf(A), vR S .

Базисным конечным автоматом для задапного регулярного языка L назовём следующую пятёрку

где:

• Q - некоторое множество пар вида таких что А е <3*, X 6 Qp и

• d - функция переходов следующего вида. Для всех у £ Q и а £ S, полагаем x~Y"y тогда и только тогда, когда: A-J-+B и Y-j+X\

вЧерез Р обозначим множество всех подмножеств данного множества. 'Определение канонического автомата приводится согласно [Melnlkov, В. On an expansion of nondetermmistic finite automata / B. Melnikov // J. of Applied Mathematics and Computing, Springer Berlin/Heidelberg. - 2007. - Vol. 24. - № 1-2].

Определение 3 Пусть даны два конечных автомата К = (ф, Е,<5,5, Р) и Т = (Ят, 5Т, {зг}> Рт) • Конечный автомат Т является всюду определённым конечным автоматом.8 Тогда обобщённая функция разметки для этих двух автоматов имеет следующий вид:

ч^-Я^тЩ.

Для двух состояний д € <Э и 9 е <5г множество (д) содержит д тогда и только тогда, когда

где - входной язык состояния <?, а ~ входной язык состояния д.9 □

Определение 4 Пусть Ь = (<Этг, ¿тг, {в*}, - канонический автомат, который эквивалентен заданному автомату К — (<Э, Е, 51, Тогда функция вида является прямой функцией разметки. О Также в литературе её принято кратко обозначать как

Определение б Обратная функция разметки - это функция вида

^■■Я-ПЯр),

для которой для любого д 6 С5 выполняется следующее равенство:

= а

Определение 6 Псевдоблок - это множество таких С} и С}р, которые являются подмножествами множеств 2 и йр соответственно, и для которых выполняется следующее:

(АфХ).

При этом если два любых множества С}' к 0?р, для которых выполняется следующее:

ассд и яРсо>рсе„

образуют псевдоблок тогда и только тогда, когда

<э' = <5 И Я'„ = ЯР,

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

'Определение вхсдаого языка можно найти в [Мельников, Б.Ф. Недетерминированные конечные автоматы / Б.Ф. Мельников // ТГУ - Тольятти - 2009].

то будем говорить, что множества Q я Qp образуют блок.

Для каждого псевдоблока b через а(Ь) обозначим соответствующие ему состояния Q С Q, а через /3(b) - соответствующие состояния Qp С Qp. При этом будем также обозначать данный псевдоблок записью b(Q, Qp). О

Определение 7 Некоторое подмножество М! множества псевдоблоков М. является покрывающим, если и только если для каждого элемента Т множества # существует псевдоблок b G М', такой что Т 6 Ь. О

Определение 8 Пусть дана таблица бинарного отношения #, построенная для двух канонических автоматов L и LR. Пусть два псевдоблока bi и Ь2> сформированных на основе таблицы отношения #, - состояния строимого конечного автомата. Допускаем возможность b¿ — b¡- Будем проводить дугу из состояния ¡>i в состояние Ь2 с пометкой a G Е при одновременном выполнении следующих двух условий:

. (Vgea(bi))(M9.a)CQ(ba)),

• (Vgem)) (Ыд,а)я№)),

где <5, и 5Р - функции переходов канонических автоматов, задающих языки L и LR соответственно. Конечный автомат, полученный таким образом, будем называть полным конечным автоматом и обозначать с помощью ÚDM(L).10

О

Определение 9 Конечный автомат К, определяющий заданный регулярный язык L, является покрывающим, если:

1. он может быть получен из автомата COM(L) удалением нескольких состояний и соответствующих дуг;

2. подмножество множества блоков, соответствующее множеству состояний автомата К, является покрывающим. Q

Определения 10 и 11 естественным образом определяют автомат с объединёнными состояниями и с продублированным состояниями соответственно.

Определение 10 Для автомата и двух его состояний qL, 92 6 Q, записью l7,1,5J(K') обозначим автомат, чей граф переходов получается из графа переходов автомата К следующим образом:

10Более подробную информацию о полном конечном автомате COM{L) можно найти в [Melniiov, В. Possible edges of а finite automaton defining the given regular language / B, Melnikov, N. Sciarini-Guryanova // The Korean Journal of Computational and Applied Mathematics. - 2002. - Vol. 9. - № 2]. Аналогичный объект, который называется универсальным автоматом, определяется в статье [Polak, L. Minimalizations of NFA Using the Universal Automaton / L. Polak // Int. Journal of Fbund. of Computer Science. - 2005. - Vol. 16.-№5].

• доя каждого г 6 5 множества дуг 7(91, г) заменяются на множества 7(д1,г)07(93,г);

• аналогично, для каждого г 6 <3 множества дуг 7(г, 91) заменяются на множества 7(г, 9^ и 7(г, <32);

• состояние 92 удаляется из автомата вместе со входящими и выходящими дугами.

Кроме того, состояние 91 автомата ¿Г51 (К) является стартовым (финальным) тогда и только тогда, когда по крайней мере одно из состояний q\ и дг является стартовым (соответственно, финальным) для К. □

Определение 11 Для автомата и его состояний 91,92,■ ■ ■ ,9п 6 <3, записью

"Я111®.....Чп(К) обозначим автомат, чей граф переходов получается из графа

переходов автомата К следующим образом:

• состояния 91,92,..., 9„ переименовываются в 91,93,..., 9„, соответственно, и добавляются состояния 91,92,...,

• дам всех ... ,г„ е <5 создаются множества 7(Й.П).7(й, п).....7(&>г0) такие, что

7(?1. П) = 7(«1> п), 7(&>г2) = 7(Й,Г2),...,7(9.1,О = 7(?п, г„);

• аналогично, для всех Г1,г2,...,г„ е '<5 создаются множества дуг 7(п>Й).7(^2,?2),••• М^тЯп) такие, что

7(П,?1) =7(^2,й).--. >7(^,9«) = 7(гп,9/.)-

Кроме того, состояния 4п автомата 7£'1,Й,",'?"(КР) являются стар-

товыми (финальными) тогда и только тогда, когда состояния 91,92,... ,9п являются соответственно стартовыми (финальными) для К. О

Рассмотрим следующий конечный автомат, изображённый на рис. 1 слева. Функция ¡р™ имеет следующие значения для состояний этого конечного автомата:

= *>}?(<?2) = !$(«>) = { А,В} , = {В}.

Значение функции у™ одинаково для двух состояний 92 и 93. Объединим эти два состояния. В результате получим конечный автомат, изображённый на рис. 1 справа.

Процесс дублирования состояний может быть продемонстрирован с помощью рис. 2. На нём слева изображён базисный автомат для языка, задаваемого регулярным выражением (а 4- аЬ + Ьа)", а справа - автомат, полученный

а в "

из базисного с помощью операции дублирования Цух состояний £ и ° базисного автомата.

Рис. 2

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

Также во второй главе приведены доказательства теорем об условиях объединения состояний.

Теорема 1 Пусть для автомата К выполнено условие

для некоторых двух его состояний q,c/ 6 Я- Тогда автомат К' — У™'(К) эквивалентен К, и

= <$(9)- а

Теорема 2 Пусть для автомата К выполнено условие

для некоторых двух его состояний q,q' £ С}'Тогда автомат К' = эквивалентен К, и

= О

Творема 3 Если для автомата К и двух его состояний <[,<?' 6 <2 выполнены следующие условия:

ч>Ш с Л) с Л),«) и ч>°ки1Ы)ФЬ,

то автомат Я' = ¿Р,'<!'(К) эквивалентен К, и

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

Теорема 4 Даны автоматы К\ и К2, которые определяют один регулярный язык. Каждый автомат имеет одну компоненту связности. С помощью конечного количества применений двух примитивов ¿Г11 л* и из К\ можно получить К^. О

В процессу доказательства этой теоремы мы получаем следующий алгоритм.

Алгоритм 1 Алгоритм построения с помощью операций объединения и дублирования состояний из заданного конечного автомата К\ другого заданного эквивалентного конечного автомата К2.

Вход: Некоторый базисный автомат 64, конечные автоматы К\ и К2, эквивалентные ВА.

Шаг 1: С помощью приведённого в диссертации вспомогательного алгоритма

по автомату К\ строим последовательность операций гщ, ш2,... ,ю„, в которой каждый элемент является примитивом ,7'ьй ддЯ некоторых 51,52 или К* для некоторого д, к базисному автомату Б4.11 Получаем конечный автомат

Шаг 2; С помощью того же вспомогательного алгоритма по автомату Кг строим последовательность операций 111, V?,... ,ит, в которой каждый элемент является примитивом ,7®1,52 для некоторых дх, д^ или 71® для некоторого д, к базисному автомату В4. Получаем конечный автомат Кг. Шаг 3: Строим последовательность операций $„,... к конечному ав-

томату К1. Любой элемент последовательности операций Ф„,... яв-

ляется обратной операцией соответствующему элементу последовательности операций №1,1112,... ,и„, применённой на шаге 1, т.е. если гих является объединением, то щ является дублированием тех же состояний, и наоборот. Получаем базисный автомат В4.

Выход: Последовательность й>„,..., щ, VI, Уз,..., ит. □

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

11 Более подробное описание последовательности операций и алгоритма её построения приведены в самой диссертации.

1гБолее подробно об этом можно найти в книге [Брауэр, Б. Введение в теорию конечных автоматов / В. Брауэр. - М. : Радио и связь, 1987/.

горитма эквивалентного преобразования13 к конечному автомату Waterloo.14 Этот алгоритм применяется для того, чтобы показать, что существуют автоматы, для которых соответствующий язык (язык полученного автомата) не совпадает с языком заданного автомата, несмотря на то, что используется покрывающее подмножество множества блоков. Во время выполнения этого алгоритма строится полный конечный автомат СОМ. Выходом стандартного алгоритма для специально выбранного подмножества множества блоков является следующий конечный автомат, заданный с помощью таблицы 1.

a b

A E -

В F -

С G В

D С H

- E С H

F - D

G A D

H A -

Табл. 1

Несмотря на то, что данный конечный автомат, построенный с помощью стандартного алгоритма, является покрывающим, его язык не равен языку заданного конечного автомата, так как отсутствует дуга а из состояния Е в состояние В в полученном конечном автомате. Таким образом, данный конечный автомат является неэквивалентным заданному. Полученный конечный автомат с помощью алгоритма 1, который использует эквивалентные преобраг зования, операции объединения и дублирования,15 является эквивалентным заданному.

m(L) a b Bi(L) a ь

- AW E#X,E#P - E#P G#V -

- A#Q E#W - - F#X - -

BW F#X,F#P - F#Z B#Y -

B#V f#z,f#r - F#P B#V -

C#u G#S B#Y,B#V F#R - D#W,D#P

c#v G#Z,G#R - G#Z AW -

D#W c#u G#R - D#W,D#P

D#P CW - 0#S A#Q -

- E#X - - B#Z AW -

E#W c#u B#Z,H#S Я#5 A#Q -

Табл.2

13 Этот стандартный алгоритм эквивалентного преобразования был взят из монографии [Мельников, Б.Ф. Недетерминированные конечные автоматы / Б.Ф. Мельников // ТГУ -ТЬльятти - 2009].

14См. рис. 3. Впервые об этом автомате упоминалось в [Kameda, Т, On the state minimization of nondeterministic finite automata / T. Kameda, P. Weiner // IEEE Trans on Computers. - 1970. - Vol. 19. - № 7. - pp. 617-627]. 15См. определения 10 и 11.

Приведём базисный автомат, построенный для конечного автомата Waterloo, с помощью таблицы 2. Заметим, что базисный автомат имеет следующий цикл:

В a F а В a F а В Y Р V *Z 'г '

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

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

Первая предложенная модель строится на.основе теоремы 4 и алгоритма 1. Она представляет собой пространство, состояния которого содержат все конечные автоматы с одной компонентой связности, определяющие один заданный язык. Для любой вершины Vj её смежная вершина Vj является либо Jqi'q:,(Vi), либо TZq(Vi). Таким образом, рёбра в описанной модели являются обозначением процедур объединения и дублирования состояний конечного автомата. Одна из вершин Vj графа G содержит базисный автомат Б4.16

Определение 12 Пространство состояний, которое является графом, отображающим модель эквивалентного преобразования конечных автоматов путём применения описанных примитивов, является следующей упорядоченной парой:

G — (V, Л),

в которой

• V - конечное непустое множество вершин. Каждая вершина V множества V содержит некоторый автомат и

• А- множество, содержащее пары различных вершин из V.

В графе G ребром а 6 А будет пара двух вершин V{ и содержащих два автомата, т.е. а = Щ, V2}) где Vj, V2 являются смежными вершинами в графе G, и выполняется одно из следующих равенств:

Va =

y2 = 7l?(Vi). □

Все автоматы, которые содержит граф G в своих вершинах, эквивалентны друг другу. Таким образом, с помощью алгоритма 1, сформулированного на основе теоремы 4, всегда можно преобразовать заданный автомат в эквивалентный автомат.

15Определение поиска в пространстве состояний на основе неориентированного графа

можно найти в [Люгер, Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание. / Д.Ф. Люгер. - М. : Вильяме, 2003. - 112 е.].

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

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

Пусть всё множество рёбер для конечного автомата К задаётся следующим образом:

А = = (р1,0},г})\р^г} € Я, а,- е а,) Э г,-, je{l,...,m}}

(где ш - количество рёбер автомата К), а всё множество рёбер для базисного автомата задаётся следующим образом:

Д = { = (ри <ц, п) |Ри г< £ <§, <к € 2, 5(р<,а{) Э п, I € {1,..., т} },

(где т - количество рёбер базисного автомата 64).17

Будем считать, что для каждого ребра с^ = (р^, а^, г,) выполняется П(е^) э е; (где П - функция вида П : Д -+ Р(6) и г 6 {1,... ,гп}), если и только если выполняются следующие три условия:

Ч = а,; э <ч.

Также пусть 0 — (ё®,..., ё£) - путь (где п - количество рёбер пути) баг зисного автомата ВА, тогда путь и = (е£,..., конечного автомата К будем называть соответствующим пути V базисного.автомата ВА, если для любого е1 — (рЬ ак1 Тк) (гДе ^ ^ {1, ■ • •, п}) выполняется следующее:

П(е£)Э

Путь V = (ё{,..., ёд) базисного автомата ВА является циклом, где е; = (р,-, а;, г\) - ребро, п - количество рёбер цикла, если г? = р\. Рассматривая цикл С = (ё(,.,,, ё£), мы получаем его п-цикл для каждого п > 1 следующим образом:

___(«Г. •. •, о.

17Функции 5 и 5 определены ранее, см. определения 1 и 2. Здесь мы рассматриваем эти функции как множества.

где дм каждого возможного г (т.е. г 6 {1,...,(п—1)-£}) мы считаем, что ё\ — Причём = . В диссертации кроме определения, также

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

т.

В пространстве состояний строится корневое дерево18 (7 для поиска состояния, включающее минимально возможно? множество блоков (или близкое к нему значение в случае эвристических алгоритмов). Корень дерева -это вершина, содержащая всё множество блоков В. Рёбра дерева отображают процедуру удаления блоков. Каждая вершина содержит подмножество В множества блоков В и всё множество циклов, которое описывается специальным образом. Определение модели поиска подмножества множества блоков В, содержащего все элементы множества бинарного отношения # и минимально возможное множество блоков, выглядит следующим образом.

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

где:

• V - конечное непустое множество вершин. Каждая вершина дерева О состоит из:

— подмножества В множества блоков В,

- множества путей или циклов;19

• А - множество, содержащее упорядоченные пары различных вершин из В.

В дереве С ребром а е А будет пара двух вершин Ц, и У2, т.е. о = (VI, где VI и являются смежными вершинами в дереве С?, 6 Ц. и Вг 6 причём Въ = ВДЬ (где Ь - блок). □

Вершина является такой структурой, по которой можно восстановить конечный автомат, так как она содержит все необходимые данные.20

''Описание поиска в пространстве состояний на основе корневого дерева можно найти в [Рассел, С. Искусственный интеллект: современный подход, 2-е издание. / С. Рассел, П. Норвиг. - М. : Вильяме, 2006. - 122-125 е.].

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

20Восстановл§ние конечного автомата можно произвести с помощью алгоритма, который

может быть получен на основе определения 9.

Схема алгоритма 2 Поиск подмножества В множества блоков В, которое содержит минимально возможное множество блоков, все элементы множества бинарного отношения # и множество простых циклов, соответствующих множеству всех простых циклов базисного автомата БД-Вход: Множество блоков В, базисный автомат В4..21 Шаг 1: Находим множество всех простых циклов базисного автомата 64. Шаг 2: Удаляем некоторый блок. Блок, который удаляется, выбирается из ещё не рассмотренных подмножеств, имеющих минимальное число блоков.22 Получаем подмножество В множества В. Шаг 3: Строим множество простых циклов подмножества BP Шаг 4: Проверяем соответствует ли множество простых циклов подмножества В множеству всех простых циклов базисного автомата ВА. Если соответствует, то переходим на шаг 2. Причём если соответствует, то подмножество В может быть текущим псевдооптимальным решением. Если не соответствует, то помечаем рассматриваемый лист как «неправильный» и больше не строим для него потомков, так как в этом случае В не может быть решением. Выход: Подмножество В множества блоков В.24 О

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

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

Определение 15 Пусть дана таблица отношения будем говорить, что в этой таблице отношения # нет одинаковых строк и столбцов тогда и только тогда, когда

• для любой строки А не существует такой строки В, в которой есть отношение # на пересечении с теми же столбцами, что и для А,

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

^Поэтому данный алгоритм является аналогом алгоритма поиска в глубину, который описан, например, в [Левитин, A.B. Алгоритмы: введение в разработку и анализ, 4-е издание. / A.B. Левитин. - М.: Вильяме, 2008, С. 212-215].

. 23Более подробно о том, что такое простые цихлы подмножества Б, налисано в тексте диссертации.

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

• для любого столбца X не существует такого столбца Y, в котором есть отношение # на пересечении с теми же строками, что и для X. О

Теорема 6 Пусть даны канонические автоматы, которые задают языки L и IP.

Тогда для этих двух языков возможна любая таблица отношения # при следующих ограничениях:

• если в «меньшем» из двух канонических автоматов, задающих языки L и Iß, имеется N состояний, то в «большем» из них - их пе более, чем 2JV — 1;

• в этой таблице отношения # нет одинаковых строк и столбцов;

• в этой таблице отношения # нет пустых строк и столбцов. D

Следующее утверждение можно считать следствием вышеупомянутой теоремы.

Утверждение 1 Если в «меньшем» из двух канонических автоматов (для

языков L и LR) имеется N состояний, то в «большем» их не более, чем 2^ — 1.

□

Теорема 7 Если и строк и столбцов не более, чем N (каждых), то число блоков не более, чем JV2. □

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

25Как упоминалось ранее, зарубежные авторы также занимаются разработкой алгоритмов, которые должны помочь в решении проблемы минимизации конечных автоматов. Например, такие алгоритмы можно найти в работе [Die, L. Reducing the size of NFAs by using equivalences and preorders / L. Hie., R. Solis-Oba, S. Yu - Springer Berlin ) Heidelberg, 2005].

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

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

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

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

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

4 Список публикаций по теме диссертации

Публикации в рецензируемых журналах, рекомендованных ВАК

1. Сайфуллина, М.Р. О построение любого конечного автомата для заданного регулярного языка с помощью базисного автомата / М.Р. Сайфуллина // Известия Самарского НЦ РАН «Технологии управления оргат низацией. Качество продукции и услуг.» - 2008. - Вып. б. - С. 70-75.

2. Мельников, Б.Ф. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов / Б.Ф. Мельников, М.Р. Сайфуллина // Известия высших учебных заведений. Математика. - 2009. - № 4. - С. 67-71. (Имеется английский перевод: Melnikov, В. F. Some algorithms for equivalent transformation of nondeterministic finite automata / B, F. Melnikov, M.R. Saifullina // Russian Mathematics (Iz VUZ). - 2009. - Vol. 53. - № 4. - pp. 54-57.)

Прочие публикации

3. Сайфуллина, М.Р. Нетрадиционные алгоритмы оптимального вычисления стейени числа / М.Р. Сайфуллина // сборник статей Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке», 27 ноября 2003 г. - Пенза : Изд-во «Приволжский Дом знаний», 2003. - С. 70-71.

4. Сайфуллина, М.Р. Эвристические алгоритмы для решения целочисленных задач дискретной оптимизации / М.Р. Сайфуллина // сборник статей XVIII Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании», 21-22 декабря 2006 г. - Пенза : Изд-во Пензенская гос. техн. академия, АНОО «Приволжский Дом знаний», 2006. - С. 6972.

5. Сайфуллина, М.Р. О получении некоторого конечного автомата, распознающего тот же регулярный язык, что и заданный с помощью базисного автомата / М.Р. Сайфуллина // сборник статей XXI Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании», 26-27 мая 2008 г. - Пенза : Изд-во Пензенская гос. техн. академия, АНОО «Приволжский Дом знаний», 2008. - С. 221-223.

Подписано в печать 20.11.2009. Формат 60x84/16 Печать оперативная. Усл. п.л. 1,4 Уч.-изд. л. 1,3. Тираж 135 экз № 3-228-09.

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

1 Введение

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

1.2 Основное содержание работы.

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

1.4 Фундаментальные понятия теории формальных языков и автоматов.

1.5 Конечные автоматы и операции над ними.

2 Алгоритмы эквивалентного преобразования автоматов

2.1 Операции объединения и дублирования состояний конечного автомата.

2.2 Построение эквивалентного конечного автомата для любого заданного с помощью базисного.

2.3 Некоторые примеры.

3 Модели эквивалентных преобразований недетерминированных конечных автоматов

3.1 Модель построения любого конечного автомата из заданного с помощью базисного автомата.

3.2 Модель поиска минимального подмножества множества блоков.

4 Бинарное отношение его свойства и минимизация

4.1 Бинарное отношение # и его свойства.

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

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

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

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

2. Формулировка и доказательство теорем о корректности этих алгоритмов и свойствах бинарного отношения

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

Объект исследования. Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева).

Предмет исследования. Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами.

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

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

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

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

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

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

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

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

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

ХС точностью до наличия лишних дуг. ковых, пустых строк и столбцов, а также если в «меньшем» нз двух канонических автоматов имеется N состояний, то в «большем» из них - их не более, чем 2N — 1.2

4. Доказательство теоремы о том, что если в таблице бинарного отношения # строк и столбцов не более, чем N (каждых), то число блоков3 не более, чем N2.

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

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

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

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

• XVIII Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2006);

• XXI Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2008);

Определения «большего» и «меньшего» автоматов приведены в 4 главе.

3Определение блока приведено в 1 главе.

• семинаре кафедры математического анализа физико-математического факультета ГОУ УлГПУ им. И. Н. Ульянова (г. Ульяновск, 2009).

• Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009). ' ~

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

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

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

1. Алёхина, М. Об одном подходе к моделированию вычислительных устройств / М. Алёхина, А. Лысенко, Б. Мельников // Известия ВУЗов, серия «Физико-математические науки» (Поволжский регион). - № 2 (2008). - С. 2-7.

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

3. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. - 535 с.

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

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

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

7. Вирт, Н. Язык программирования ПАСКАЛЬ// Алгоритмы и организа- ция решения экономических задач / Н. Вирт. -М.: Статистика, 1974. 410 с.

8. Гилл, А. Линейные последовательностные машины. Анализ, синтез и применение / А. Гилл. М.: Наука, 1974. - 287 с.

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

10. Грунский, И. Анализ поведения конечных автоматов / И.Грунский. -Луганск: Изд-во ЛНПУ, 2003. 318 с.

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

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

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

14. Левитин, А.В. Алгоритмы: введение в разработку и анализ, 4-е издание. / А.В.Левитин. М.: Вильяме, 2006. - 212-215 с.

15. Лекции лауреатов премии Тьюринга за первые двадцать лет: сб. ст. / М.: Мир, 1993. 560 с.

16. Люгер, Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание. / Д.Ф. Люгер. М.: Вильяме, 2003. -212-215 с.

17. Медведев, Ю. О классе событий, допускающих представление в конечном автомате / Ю. Медведев // Автоматы. М.: Иностранная Литература, 1956. - С. 385-401.

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

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

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

21. Мельников, Б. Ещё раз о конечных автоматах / Б. Мельников // Учёные записки Ульяновского государственного университета. Фундаментальные проблемы математики и механики. Вып. 1, ч. 2. 1996. - С. 1323.

22. Мельников, Б. Ещё раз об объединении состояний недетерминированного конечного автомата / Б. Мельников // Тезисы докладов XI международной научной конференции по проблемам теоретической кибернетики. М.: Изд-во РГГУ. - 1996. - С. 139-141.

23. Мельников, Б. Сведение задач минимизации конечных автоматов к работе с орграфами / Б. Мельников, А. Бросалина // «Математическое моделирование физических, экономических, социальных систем и процессов». Изд-во Ульяновского ун-та, 1998. - С. 15.

24. Мельников, Б. Важный пример к задачам минимизации недетерминированных конечных автоматов / Б. Мельников // Тезисы докладов XII международной научной конференции по проблемам теоретической кибернетики. М.: Изд-во МГУ. - 1999. - С. 153-153.

25. Мельников, Б. Эвристические алгоритмы в специальных задачах дискретной оптимизации / Б. Мельников, А. Радионов // «Дискретный анализ и исследование операций». Новосибирск, Изд-во Института математики, 2000. - С. 190.

26. Мельников, Б. Эвристики в программировании недетерминированных игр / Б. Мельников // Программирование (РАН). 2001. - № 5. - С. 6380.

27. Мельников, Б. Ещё раз об эвристиках для задачи коммивояжёра / Б. Мельников, Н. Романов // Теоретические проблемы информатики и её приложений, вып. 4. Изд-во Саратовского университета, 2001. -С. 81-92.

28. Мельников, Б. Однозначные конечные автоматы / Б.Мельников // Известия ВУЗов, серия «Технические наукрт» (Поволжский регион). -2002. № 2. - С. 9-14.

29. Мельников, Б. Об ш-языках специальных биллиардов / Б. Мельников // Дискретная математика (РАН). 2002. - № 3. - Т. 14. - С. 95-108.

30. Мельников, Б. Программирование недетерминированных игр / Б. Мельников // Российская наука: дорога жизни. Изд-во Октопус.- 2003. С.23-32.

31. Мельников, Б. Мультиэвристический подход к задачам дискретной оптимизации / Б. Мельников // Кибернетика и системный анализ (НАН Украины). 2006. - № 3. - С. 32-42.

32. Мельников, Б. Недетерминированные конечные автоматы / Б. Мельников // ТГУ Тольятти. - 2009. - № 3. - С. 32-42.

33. Мельников, Б. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов / Б.Мельников, М. Сайфуллина // Теоретические проблемы информатики и её приложений, вып. 4. Известия ВУЗов, Математика. - 2009. - № 4. - С. 67-71.

34. Новиков, Ф. Дискретная математика для программистов / Ф.Новиков.- СПб: Питер, 2002. 304 с.

35. Разборов, A. Theoretical Computer Science: взгляд математика / А. Разборов // Компьютерра. 2001. - № 2. - С. 39-46.

36. Рассел, С. Искусственный интеллект: современный подход, 2-е издание. / С. Рассел, П. Норвиг. М.: Вильяме, 2006. - 122-125 с.

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

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

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

40. Харари, Ф. Теория графов / Ф.Харари. М.: Мир, 1973. - 300 с.

41. Хопкрофт, Дж. Алгоритм для минимизации конечного автомата, Кибернетический сборник, новая серия, вып. 11 / Дж.Хопкрофг. -М.: Мир, 1974. 177-184 с.

42. Чирков, М. Основы общей теории конечных автоматов / М. Чирков.- Л.: Изд-во ЛГУ, 1975. 280 с.

43. Шень, А. Программирование: теоремы и задачи / А. Шень. М.: Изд-во МЦНМО, 2004. - 285 с.

44. Яблонский, С. Дискретная математика / С. Яблонский. — М.: Наука, 1979. 272 с.

45. Языки и автоматы / М. :Мир, 1975. 358 с.

46. Bellmore, М. The Traveling Salesman Problem: A Survey / M. Bellmore, G. Nemhauser // Operation Reasearch. Vo.16 (1968). - P. 538-558.

47. Belov, A. Monomial algebras / A. Belov, V. Borisenko, V. Latyshev // Journal of Mathematical Sciences (New York). 87 (1997), No. 3. - P. 34633575.

48. Bergman, G. The Diamond Lemma for Ring Theory / G.Bergman // Advances in Mathematics. 29 (1978). - P. 178-218.

49. Brzozowski, J.A. Open problems about regular languages, In: Ronald V. Book, editor, Formal language theory—Perspectives and open problems / J.A. Brzozowski. N. Y.: Academic Press, 1980. - 23—47 c.

50. Chomsky, N. Finite state languages, Inform, and Control / N. Chomsky, G.A. Miller. M.: Мир, 1962. - 233-255 с.

51. Eilenberg, S. Automata, Languages and Machines. Vol. A / S.Eilenberg. N. Y.: Academic Press. 1974. - 312 c.

52. Dejean, F. On a question of Eggan / F. Dejean, M. Schutzenberger. — Information and Control 9(1), 1966. 23-25 c.

53. Hashiguchi, K. Algorithms for determining relative star height and star height / K. Hashiguchi // Inform. Comput. 78 (1987). - P. 124-169.

54. Hromkovic, J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics / J. Hromkovic. Springer, 2004. - 548 c.

55. Jiang, T. Minimal NFA Problems are Hard / T.Jiang, B.Ravikumar // SIAM J. Comput. 22 (1993). - P. 1117-1141.

56. Kameda, T. On the state minimization of nondeterministic finite automata / T. Kameda, P. Weiner // IEEE Trans, on Computers. C-19 (1970). -P. 617-627.

57. Eggen, L.C Transition graphs and the star-height of regular events / L.CEggen // The Michigan Mathematical Journal. 1963. - P. 385-397.

58. Mealy, G.H A Method to Synthesizing Sequential Circuits / G.H Mealy // Bell Systems Technical Journal. 1955. - P. 1045-1079.

59. Melnikov, В. Some more on the finite automata / B. Melnikov,A.Vakhitova // The Korean Journal of Computational and Applied Mathematics. 5 (1998) No. 3. - P. 495-506.

60. Melnikov, B. A new algorithm of the state-minimization for the nondeterministic finite automata / B. Melnikov // The Korean Journal of Computational and Applied Mathematics. 6 (1999) No. 2. - P. 277-290.

61. Melnikov, B. Once more about the state-minimization of the nondeterministic finite automata / B. Melnikov // The Korean Journal of Computational and Applied Mathematics. 7 (2000) No. 3. - P. 655-662.

62. Melnikov, B. Edge-minimization of non-deterministic finite automata /B. Melnikov, A. Melnikova // The Korean Journal of Computational and Applied Mathematics. 8 (2001) No.3. - P. 469-479.

63. Melnikov, B. Some properties of the basis finite automaton / B. Melnikov, A. Melnikova // The Korean Journal of Computational and Applied Mathematics. 9 (2002) No. 1. - P. 131-150.

64. Melnikov, B. Possible edges of a finite automaton defining the given regular language / B. Melnikov, N. Sciarini-Guryanova // The Korean Journal of Computational and Applied Mathematics. 9 (2002) No. 2. - P. 475-485.

65. Melnikov, B. Discrete optimization problems some new heuristic approaches / B. Melnikov // IEEE Сотр. Soc. Press Ed. -2005. - P. 73-80.

66. Melnikov, B. Some special heuristics for discrete optimization problems / B. Melnikov, A. Radionov, V. Gumayunov // The 8th International Conference on Enterprise of Information Systems. 2006. - P. 91-95.

67. Moore, E.F. Gedanken-experiments on Sequential Machines. Automata Studies,Annals of Mathematical Studies / E.F.Moore. Princeton, N.J.: Princeton University Press, 1956. - 129—153 c.

68. Polak, L. Minimalizations of NFA using universal automata / L. Polak // Int. J. of Found, of Computer Science. 16 (2005) No. 5. - P. 999-1010.

69. Pcrrin, D. Finite Automata. Handbook of Theoret. Comput. Sci., Vol. A / D. Perrin. Elsevier Sci. Publ., 1990. - 1-57 c.

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

71. Staiger, L. cj-Languages. Handbook of Formal Languages, Vol.3 / L. Staiger // Berlin : Springer. 1997. - P. 339-387.

72. Stanevichene, L.I. An algorithm for transformation of finite automata to regular expressions / L.I. Stanevichene, A.A. Vylitok // Informatica. 11 (2000) No. 1. - P. 49-54.

73. Thomas, W. Automata on Infinite Objects / W.Thomas // Handbook of Theoret, Comput. Sci., Vol.B, Elsevier Sci. Publ. 1990. - P. 133-191.

74. Vakhitova, A. The basis automaton for the given regular language / A. Vakhitova // The Korean Journal of Computational and Applied Mathematics. 6 (1999) No. 3. - P. 617-624.

75. Wood, D. Grammar and L Forms: an Introduction / D.Wood. -Berlin : Springer, 1980. 328 c.