Содержание к диссертации
Введение
1 Введение 4
1.1 Исторический обзор, актуальность и новизна темы 4
1.2 Применяемые обозначения 12
1.3 Структура диссертационной работы 17
Базисные автоматы – определения... 21
2.1 Дополнительные определения и обозначения 21
2.2 Базисный автомат – определение 22
2.3 Функции разметки состояний 23
2.4 Первый пример построения... 27
2.5 Основное утверждение... 31
2.6 Однозначность базисного автомата 34
2.7 Свойство допускающего пути произвольного НКА . . 38
2.8 Примеры построения базисного автомата 39
2.9 Альтернативный алгоритм... 46
3 Свойства базисных автоматов 50
3.1 Свойства функций разметки 51
3.2 Варианты алгоритмов объединения состояний 53
3.3 Примеры применения... 55
3.4 Изменение значений функций разметки... 58
3.5 Свойства входных и выходных языков 60
3.6 Ещё раз о бинарном отношении # 64
4 Задачи минимизации ... 71
4.1 Блоки и псевдоблоки 72
4.2 Множество возможных дуг 74
4.3 Первый алгоритм дуговой минимизации 80
4.4 Второй алгоритм дуговой минимизации 86
5 Заключение 89
Литература
- Применяемые обозначения
- Функции разметки состояний
- Варианты алгоритмов объединения состояний
- Первый алгоритм дуговой минимизации
Применяемые обозначения
Обоснованность и достоверность основных научных результатов диссертационного исследования обеспечивается строгостью постановок задач и математических методов их решения, подтверждается приведёнными в диссертации доказательствами утверждений и теорем.
Основные положения, выносимые на защиту Определение функций разметки состояний заданного конечного автомата и формулировка свойств этих функций. Определение базисного конечного автомата как инварианта регулярного языка, альтернативного каноническому автомату. Описание двух алгоритмов построения базисного конечного автомата. Формулировка свойств базисного конечного автомата; среди них: – эквивалентность базисного автомата и канонического; – однозначность базисного автомата – т.е. единственность последовательности состояний базисного автомата при принятии им некоторого слова рассматриваемого языка; – утверждение о связи любого допускающего пути любого автомата, определяющего заданный регулярный язык, с соответствующим путём базисного автомата.
Доказательство соответствующих утверждений о свойствах функций разметки состояний и базисного автомата. Утверждения о свойствах таблицы состояний конечного автомата. Описание двух алгоритмов дуговой минимизации недетерминированных конечных автоматов на основе определения базисного конечного автомата. Доказательство корректности описанных алгоритмов.
Основные научные и практические результаты диссертации были представлены на следующих российских и международных научных конференциях и семинарах. Научная конференция «Математическое моделирование физических, экономических, социальных систем и процессов», Ульяновск, УлГУ, 1998 и 1999 г. Международная алгебраическая конференция памяти А.Г.Куроша, Москва, МГУ, 1998 г. VII Международный семинар «Дискретная математика и её приложения», Москва, МГУ, 2001 г. Международная научно-практическая конференция «Методы и алгоритмы прикладной математики в технике, медицине и экономике», Новочеркасск 2001 г. Научный семинар для аспирантов кафедры МАТИС (под руководством д.ф.-м.н. В.Буевича и С Алёшина), Москва, МГУ, 2001 и 2002 г.г. Научный семинар (под руководством д.ф.-м.н. Г.Осипова), Переславль-Залесский, ИПС ГАН, 2001 и 2003 г.г. XIII Международная конференция «Проблемы теоретической кибернетики», Казань, 2002 г. Международная научно-практическая конференция «Проблемы математического образования и культуры», Тольятти, ТГУ, 2003 г. Международная конференция «Общие проблемы управления и их приложения. Проблемы преподавания математики» Тамбов, ТГУ, 2007 и 2009 г.г. Научный семинар по математической кибернетике и дискретной математике при Диссертационном совете Д 212.081.24, Казань, КГУ (КПФУ), 2009-2014 г.г.
Научный семинар кафедры математического анализа Ульяновского государственного педагогического университета, 2010 и 2012 г.г. Научный семинар по дискретной математике, Димитровград, Филиал УлГУ и ДИТИ - филиал Научно-исследовательского ядерного университета «МИФИ», 1999-2014 г.г. Публикации
Основные результаты диссертации опубликованы в 21 работе, 7 из которых входят в список изданий, рекомендованных ВАК. Личный вклад
Изложенные утверждения и теоремы доказаны лично автором, либо совместно с научным руководителем. Результаты, полученные в совместных с научным руководителем работах [34, 36, 37, 38, 94, 95, 96, 100], принадлежат в части, касающейся базисных автоматов, автору диссертации.
Итак, в данной диссертационной работе рассматриваются недетерминированные автоматы Рабина-Скотта. Различные варианты изложения теории конечных автоматов (например - варианты обозначений) см., например, в монографиях [6, 19, 64]. В данной диссертации будут применяться обозначения, согласованные с публикациями автора. При этом важно отметить, что они во многом не совпадают с применёнными в [32]: в [32], они были построены на основе некоторого рассматриваемого автомата, а в настоящей диссертации они построены на основе некоторого рассматриваемого регулярного языка.
Функции разметки состояний
Рассмотрим определения прямой и обратной функций разметки, которые применяются при построении бинарного отношения , при построении базисного автомата, а также могут применяться при решении многих других задач. Впервые эти функции были введены в работе автора [8].
Последнее определение можно считать и алгоритмом построения функции (p%KZ, поскольку x(q) и C%z{?[) – регулярные языки. Отметим, что в процессе построения эквивалентного канонического автомата, выполненного специальным образом, можно получить и более простой алгоритм построения этой функции, что используется в примерах раздела 2.8 данной диссертации.
Для канонического автомата эквивалентного заданному автомату К, функцию (рг (т.е. когда рассматриваемые автоматы, исследуемый и канонический, эквивалентны) будем кратко обозначать ср и называть прямой функцией разметки.
Именно функция (fix и будет чаще всего использоваться в дальнейших построениях. Кроме того, в дальнейшем изложении через QTT, как и ранее, будет обозначаться множество состояний канонического автомата, эквивалентного заданному,2 а во всех рассматриваемых далее примерах мы будем строить именно функцию (fift. Либо канонического автомата, определяющего заданный регулярный язык зависимости от рассматриваемой нами задачи.
Теперь рассмотрим канонический автомат, допускающий язык LR (как было отмечено, Qp - множество состояний этого автомата), и функцию (fiftR. По введённому нами определению (ргп, эта функция имеет вид
Оставшиеся две пары состояний не подходят - это можно несложно доказать, например, пользуясь известным алгоритмом сравнения двух регулярных языков3. Таким образом, нами построена следующая функция ср :
Продолжим рассмотрение этого же примера дальше. Рисунок для автомата KR приводить не будем; также опускаем детали процедур детерминизации и канонизации. Эквивалентный автомату KR канонический автомат (согласно, введённым обозначениям - LR) изображён на рис. 4:4 [2] и мн.др.; отметим, что при этом можно применять модификацию ал горитма канонизации автомата, приведённую во введении. Отметим следующее важное обстоятельство (см. также соответствующую сноску в [32]). В большинстве работ автора и научного руководителя (опубли кованных до [47, 90] и т.п.) применяется обозначение KR вместо LR. Аналогичные замены обозначений в настоящей диссертации проведены и в других местах, где можно считать, что рассматриваемый автомат строится не для какого-либо конкретного «входного» автомата К, а для «входного» языка L, обычно соот ветствующего «входному» автомату. Например - ниже вместо L можно было бы писать К . По-видимому, именно последние применяемые нами обозначения несколько более логичны.
Рассмотрим также зеркальный автомат для Ьд, т.е. f LR 1 - см. рис. 5. Вообще, автомат ( LR 1 будет использоваться далее очень часто, по-этому, как было отмечено выше, мы будем иногда вместо I LR) крат ко писать L . Заметим, что произвольный автомат К эквивалентен построенному на его основе L .
Таким образом, в данном случае канонический автомат, допускающий инверсный (зеркальный) язык, также имеет 2 состояния (обозначенные на рисунке X и Y). Аналогично проведённым ранее построениям, получаем следующую функцию ср1 1:
Первый пример построения базисного автомата В этом разделе мы рассматриваем подробный пример построения базисного автомата для языка, заданного регулярным выражением (а + аЪ + Ьа) . Граф переходов автомата К, одного из НКA, задающих данный регулярный язык, показан на рис. 6. Изменив на этом рисунке направления стрелок на противоположные, получим граф переходов зеркального к К автомата KR, задающего инверсный язык LR.
Соответствующий конечный автомат в канонической форме - L. В данной диссертационной работе и в предыдущих публикациях автора не рассматривается единственно возможное бесполезное состояние автоматов в канонической форме. При этом смысл всех построений практически не меняется, но их формулировка становится менее громоздкой. Несложно доказывается, что для бесполезных состояний канонических автоматов (пусть это М для автомата L и N для автомата LR) и для любых состояний не может выполняться ни условие N#X, ни A#N (ни для каких состояний А Є Q и X Є Qp этих автоматов). Поэтому бесполезное состояние не может входить в состояние базисного автомата - в качестве элемента пары (А,Х). Следовательно, и в графах переходов канонических автоматов мы также не будем указывать бесполезные состояния - это делает граф более наглядным.
Варианты алгоритмов объединения состояний
В этом разделе приведён альтернативный алгоритм построения дуг базисного автомата. Кратко опишем его, применяя следующие обозначения. Дуги автоматов L и LR будем обозначать заглавными греческими буквами, не совпадающими по написанию с латинскими - до буквы S для автомата L и начиная с буквы П для автомата Ьд, а также для зеркального к последнему автомата (LR 1 . Для некоторой конкретной дуги Г, идущей из вершины А в вершину В и имеющей пометку а Є S, будем писать аа(Г) = А и /За(Г) = В.
Итак, выберем произвольную букву а Є Е; описанную здесь процедуру мы проделаем для каждой буквы алфавита. Пусть 6% - помеченные буквой а дуги автомата L (т.е. элементы множества 6 ), а Ьа -помеченные буквой а дуги автомата LR (т.е. элементы множества 5р). Аналогично сказанному выше, будем таким же образом обозначать соответствующее множество дуг автомата f LR 1 . Рассмотрим бинарное отношение а С 5% х др, определённое следующим образом. Для некоторых Г є 6% и Q є 5р полагаем T#aQ тогда и только тогда, когда для некоторого слова w Є L имеем представление w = uav, и при этом:
Как и ранее в аналогичных случаях (например, при определении отношения , определении базисного конечного автомата и др.), приведённое нами определение отношения а с помощью (2.10) можно рассматривать как алгоритм его построения.
Доказательство. Как и при формулировке отношения а, считаем некоторую букву а Є Е зафиксированной.
Перепишем условие T#aQ (т.е. (2.10)) другим способом. После выбора конкретных слов и и v в (2.10) - а такие слова действительно существуют, это следует из способа построения автоматов L и L -первое и третье «подусловия» этого условия можно переписать следующим образом: при этом форма записи именно такая - поскольку мы применяли функции аа и f3a к Г, рассматривая последнюю как дугу не автомата Ьд, а автомата L . Объединяя условия (2.12) и (2.13), получаем (2.11).
Рассмотрим пример - построение того же базисного автомата, который мы получили в разделе 2.4, с помощью описанного в данном разделе алгоритма. Для этого сначала приведём графы переходов автоматов L и L . Сами графы переходов этих автоматов уже были рассмотрены выше, однако в данном разделе нам нужны обозначения дуг. Итак, автоматы L и L - вместе с обозначениями дуг заглавными греческими буквами - даны на рисунках 19 и 20 соответственно: одноимённым дугам автомата
В ней парам дуг автоматов L и L поставлены в соответствие слова рассматриваемого языка, и при этом - в случае, когда в слове более одной буквы а, - подчёркнута та буква а этого слова, читая которую автоматы (напомним, что они оба - однозначные) проходят по этим дугам. (Конечно же, в клетки таблицы можно вписать и другие слова рассматриваемого языка; нами выбраны минимальные по длине.)
Отсутствие соответствующего слова для пары дуг 0 и Ф можно было бы показать, описав (например, с помощью детерминированных конечных автоматов) входные языки состояний С и X (откуда выходят эти дуги) - после чего показав пустоту пересечения этих языков. Однако в частных случаях - в том числе в рассматриваемом нами -задача решается существенно проще. В данном случае, как видно из рис. 19, автомат L в процессе своей работы проходит по дуге О в одном из следующих двух случаев: либо прочитав Ъ в качестве первой буквы рассматриваемого слова, либо прочитав ЪЪ. В обоих этих случаях автомат L , как видно из рис. 20, оказывается в вершине У, а не X.
Итак, мы получили 8 элементов бинарного отношения а. Покажем, как с помощью этих элементов получаются те же дуги базисного автомата, которые ранее были получены в рассмотренном примере раздела 2.4. Для этого рассмотрим следующую таблицу 12, в которой в клетке, соответствующей паре дуг автоматов L и L , запишем дугу базисного автомата согласно (2.11):
Эта глава посвящена основным свойствам базисных конечных автоматов и некоторым алгоритмам работы с ними, а также их применению в различных задачах теории регулярных языков. Отметим, что все доказанные в этой главе утверждения применяются во всех трёх вышеназванных задачах минимизации - причём как в точных, так и в эвристических алгоритмах.
Итак, в данной главе рассматриваются свойства базисных конечных автоматов и функции разметки состояний. Некоторые из таких свойств устанавливают связь между входными и выходными языками состояний - произвольного недетерминированного конечного автомата, определяющего заданный регулярный язык, а также канонических автоматов. определяющих заданный регулярный язык. В главе также доказаны некоторые свойства таблицы соответствия состояний - в частности, показано, что некоторые «естественные» необходимые ограничения на эту таблицу фактически формулируют необходимые и достаточные условия существования соответствующего регулярного языка - т.е. языка, обладающего такой таблицей
Первый алгоритм дуговой минимизации
Перебирая подмножества множества 5 , определить то из них (искомое множество 8), при котором полученный автомат: – действительно определяет язык L; – имеет минимально возможное число дуг.
Утверждение 25 Язык автомата, построенного согласно алгоритму 2, содержит заданный язык L как подмножество.
Доказательство несложно, приведём лишь его схему. Рассматривая любую вершину полученного автомата (пусть автомат - К, вершина - д), для этой вершины - любую пару значений её функций разметки (пусть (А,Х)) и любое слово языка gW) ), где Т = (А,Х), мы показываем индукцией по длине данного слова, что оно принадлежит языку Cjn(q).
Аналогично доказываются соответствующие факты про выходные языки, Cout. Объединяя утверждения про входные и выходные языки, получаем искомый факт. D
Заметим, что автомат, полученный в алгоритме 2 с функцией переходов 6 , вообще говоря, не определяет заданный язык L. Например, Построение автомата с функцией переходов 8 в данном алгоритме можно неформально описать следующим образом. Для заданного языка строим базисный автомат, после чего делаем в нём копии всех вершин - в количестве, равном количеству вхождений пары функций разметки состояний вершины в блоки. Далее объединяем «размноженные» вершины согласно описанию множества блоков. Таким образом мы описываем ещё один возможный вариант применения исследуемых в настоящей диссертации базисных автоматов. Подробнее о таком применении см. [16]. (все обозначения совпадают с применёнными ранее, в том числе - с обозначениями псевдоблоков с помощью символа В). Однако способ построения автомата и утверждение 25 дают возможность переборного построения минимального автомата, т.е. справедлива следующее утверждение.
Утверждение 26 Алгоритм 2 даёт автомат, определяющий заданный регулярный язык и имеющий минимально возможное число дуг.
Доказательство. Согласно определению множества дуг д , каждая из дуг этого множества входит во множество возможных дуг, построенное ранее в разделе 4.2. Согласно описанию алгоритма, построенный автомат определяет язык L. Эти утверждения обосновывают минимальность автомата (с точки зрения числа дуг), строимого алгоритмом. D
В заключении главы отметим, что базисный автомат и описание второго варианта алгоритма дуговой минимизации НКА используются: в построении т.н. расширенного базисного автомата ([91]), который, в свою очередь, используется в описании алгоритмов для точного решения задач минимизации, а также в эвристических алгоритмах для аналогичных задач; в описании алгоритма дуговой минимизации на основе не множества псевдоблоков, а множества блоков ([92]). Основные результаты диссертации Определены прямая и обратная функции разметки состояний недетерминированных конечных автоматов. Исследованы основные свойства этих функций. Определён инвариант регулярного языка – базисный конечный автомат, являющийся альтернативой другому инварианту регулярного языка – каноническому конечному автомату. Описаны два алгоритма построения базисного конечного автомата, показана корректность этих алгоритмов.
Исследованы свойства базисного конечного автомата: – доказана эквивалентность базисного автомата и канонического, а также однозначность базисного автомата; – доказано утверждение о связи любого допускающего пути любого автомата, определяющего заданный регулярный язык, с соответствующим путём базисного автомата; – доказаны утверждения о свойствах функций разметки.
Доказаны утверждения о свойствах таблицы состояний конечного автомата; основным из них является описание алгоритма построе ния регулярного языка по заданной таблице бинарного отношения
