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



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

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

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

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

Тольятти - 2010

004606108

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

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

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

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

профессор Соколов Андрей Владимирович

кандидат технических наук Крайнюков Николай Иванович

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

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

Защита диссертации состоится 1 июля 2010 года в 12.00 на заседании диссертационного совета Д 212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14. >■

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

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

Автореферат разослан * » мая 2010 года Учёный секретарь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где:

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

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

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

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

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

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

4Через V обозначим множество всех подмножеств данного множества.

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

f-.QxQ^-ViV и{г}). Функция 7 задаётся по 5 следующим образом:

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

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

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

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

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

Бинарное отношение # (где # С Qr х Qp) определяется следующим образом для пары состояний автоматов L и LR\

А#Х если и только если (Зад 6 ь) (и е Cf(A), vR € С~(Х)) .

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

Ш (L) = (&Z,6,S,F),

где:

• Q - некоторое множество пар вида таких что А е Qn, X € Qp и А#Х;

• 5 - функция переходов следующего вида. Для всех 6 Q и а £ S,

полагаем i —тогда и только тогда, когда: А-^-уВ и Y-^-X;

S in If

. S = { J|eir#x};

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

Определение 3 . Пусть даны два конечных автомата К = ( Q, Е, S, S, F) и T = (Qr,E, 6т, {sr}, F?) ■ Конечный автомат Т является всюду определённым конечным автоматом.6 Тогда обобщённая функция разметки для этих двух автоматов имеет следующий вид:

<Р% ■ Q ^ V(Qt) ■

Для двух состояний q £ Q и q е QT множество ¥>$"(<?) содержит q тогда и только тогда, когда

где С%к{д) - входной язык состояния q, a £^{q) - входной язык состояния q.1

Определение 4 . Пусть L = (Q)r,E,5,r,{s,r},.F,r) - канонический автомат, который эквивалентен заданному автомату К = (Q, Е,<5,5, F). Тогда функция вида f1^ является прямой функцией разметки. Также в литературе её принято кратко обозначать как ip™.

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

V^-.Q-ïViQr), для которой для любого g 6 О выполняется следующее равенство:

Определение 6 . Псевдоблок - это множество таких Q„ и Qp, которые являются подмножествами множеств Q„ и Qp соответственно, и для которых выполняется следующее:

(VAeQ^XeQ,) (А#Х).

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

Q-rÇ&ÇC, и QPçQ'pçQp, образуют псевдоблок тогда и только тогда, когда

су^я* и Q'p = Qp,

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

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

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

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

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

Определение 8 . Пусть дана таблица бинарного отношения #, построенная для двух канонических автоматов L и LR. Пусть два псевдоблока bj и ¿2, сформированных на основе таблицы отношения #, - состояния строимого конечного автомата. Допускаем возможность fa = b2. Будем проводить дугу из состояния bi в состояние Ь2 с пометкой а £ Е при одновременном выполнении следующих двух условий:

• (Уд€ a(h)) (8,(q, а) С а(Ь2)),

• (V?e/3(b2))(5,(g,a)C Щ)),

где 6„vi5p- функции переходов канонических автоматов, задающих языки L и Lr соответственно. Конечный автомат, полученный таким образом, будем называть полным конечным автоматом и обозначать с помощью СОМ{Ь).г

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

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

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

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

I

Определение 10 . Для автомата и его состояний ...........Яп € Q записью

обозначим автомат, чей граф переходов получается из графа переходов автомата К следующим образом:

• для каждого г € Q множества дуг 7(91,г),7(52, r),-..,7(?m>') заменяются на множества дуг 7(91, г) U 7(52, r)U,..., U7(g„, г);

• аналогично, для каждого г 6 Q и каждое из множеств дуг 7(г, q{), 7(г, ft), • • •, f(r, q„) заменяется на множества дуг

1 (г, ft) U у (г, q2) U,..., U7 (г, д„);

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

• состояния <72,..., qn удаляются из автомата вместе со входящими и выходящими дугами.

Кроме того, состояние gi автомата .....Я"(К) является стартовым

(финальным) тогда и только тогда, когда по крайней мере одно из состояний 9ъ 92, • • • I 9п является стартовым (финальным) для К.

Определение 11 . Для автомата и его состояний <ji, ^ ■ • ■ i 9п 6 Q\ записью

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

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

• состояния <ji, .....In переименовываются в 92,• • •, 9п>

соответственно, и добавляются состояния 91,92,

• для всех гх,Г2, ■ ■ ■ ,гп € Q создаются множества

... п) такие, что

l{qi,ri) =7(й.п), 7(92, г2) = 7(92, г2),...,7(9п,г„) =7(9п,г„);

• аналогично, для всех ri,ra,...,r„ € Q создаются множества дуг 7(n, й), 1{гг, <й), • • •, l{rn, in) такие, что •

7(n> 9i) = 7(n, 9i)< 7(^2, й) = 7(Гг, 9з), • • •, 7(rn> 9n) = 7(rn. ?»)•

Кроме того, состояния gi, ..., ^ автомата 7являются стартовыми (финальными) тогда и только тогда, когда состояния 91,92, • • ■, 9п являются соответственно стартовыми (финальными) для ЛГ.

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

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

vJ?(«i) = {Л}, = = { Л В }, <(94) = {В}.

,<п,

с

а,Ь, е 6

Рис. 1

Процесс дублирования состояний может быть продемонстрирован с

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

задаваемого регулярным выражением (а + аЬ + Ьа)*, а справа - автомат,

л в

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

Рис. 2

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

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

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

¥>]?(?) = ¥#(90

для некоторых двух его состояний д, (/ 6 ф. Тогда автомат К' эквивалентен К, и

А) = ¥>$(9). 0 Теорема 2 . Пусть для автомата К выполнено условие

для некоторых двух его состояний д, д1 6 <3- Тогда автомат К' эквивалентен К, и

=

= з "¿{К) '

Теорема 3 . Если для автомата К и двух его состояний д, 4 6 Я выполнены следующие условия:

с £ ¥#"(?)■ * 0 и р°Ля') * 0 -

то автомат К' = эквивалентен К, и

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

Теорема 4 . Даны автоматы К\ и Яг, которые определяют один регулярный язык. Каждый автомат имеет одну компойенту связности. С помощью конечного количества применений двух примитивов и цч из МОжно получить Кг? О

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

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

Алгоритм 1 . Алгоритм построения с помощью операций объединения и дублирования состояний из заданного конечного автомата К\ другого заданного эквивалентного конечного автомата ЛГ2.10 Вход: Некоторый базисный автомат В4, конечные автоматы К\ и эквивалентные 54.

Шаг 1: С помощью приведённого в диссертации вспомогательного алгоритма по автомату К\ строим последовательность операций ги2,. ■ ■, 1ип, в

которой каждый элемент является примитивом У41'1"....... для некоторых

9ь92| • • • 1<?п или для некоторого д, к базисному автомату 64.11 Получаем конечный автомат

Шаг 2: С помощью того же вспомогательного алгоритма по автомату К2 строим последовательность операций в которой каждый

9 С точностью до наличия лишних дуг.

10С точностью до наличия лишних дуг.

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

элемент является примитивом ,7«-«.....з* длЯ некоторых 91,92,... ,дп или V?

для некоторого 5, к базисному автомату В4. Получаем конечный автомат К,.

Шаг 3: Строим последовательность операций ь}„,... к

конечному автомату К\. Любой элемент последовательности операций й>п,... ,щ,й>\ является обратной операцией соответствующему элементу последовательности операций гииЩ>---, применённой на шаге 1, т.е. если Ш] является объединением, то щ является дублированием тех же состояний, и наоборот. Получаем базисный автомат ВА. Выход: Последовательность □

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

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

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

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

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

а Ь

-v А Е -

В F -

С G В

D С н

Е С н

<- F - D

G А D

Н А -

Тайл. 1

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

В4(1) а ъ m{L) a b

- A#Y Е#Х,Е#Р - E#P c#v -

- A#Q E#W - - F#x - -

В#У F#X,F#P - F#Z B#Y -

BW F#Z,F#R - F#P B#V -

с#и G#5 F#R - D#W,D#P

cw G#Z,G#R - G#Z AW -

D$W C#U H#Z,H#S G#R - £>#W,0#P

D#P C*v - G#S A#Q -

~ Е#Х - - H#Z AW -

c#u tf#Z,H#S H#s A#Q -

Табл. 2

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

В о ч F a.F а ^В

у 'у >г Y '

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

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

1sCm. определения 10 и 11.

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

Первая предложенная модель строится на основе теоремы 4 и алгоритма 1. Она представляет собой пространство состояний, вершины которого содержат все конечные автоматы с одной компонентой связности, определяющие заданный язык. Для любой вершины V] её смежная вершина Уз является либо У1'®3^), либо ТУЧУх). Таким образом, рёбра в описанной модели являются обозначением процедур объединения и дублирования состояний конечного автомата. Одна из вершин Ц графа <3 содержит базисный автомат £4.16

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

в которой

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

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

В графе С ребром а € А будет пара двух вершин и содержащих два автомата, т.е. а = {VI, Ц}, где VI, У2 являются смежными вершинами в графе О, и выполняется одно из следующих равенств:

У2 =

V* = 7^(14).

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

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

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

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

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

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

А = = (Pj.aj.rj) \Pj.rj е <2, а,- е 2, а,) э ^ е {1,... ,го}}

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

А = { ё{ = (ри4i.fi) lft.fi 6 4 <4 е Я, аО Э п, г € {1,... ,т} },

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

Будем считать, что для каждого ребра ц = (Pj.aj.Tj) выполняется П(е^) Э ëi (где П - функция вида П : Д -» Т(5) и % £ {1,..., т}), если и только если выполняются следующие три условия:

а,- = а,; Э п .

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

Путь V = (ё{, ■■■ ,е°л) базисного автомата 64 является циклом, где = {риаип) - ребро, п - количество рёбер цикла, если т^ = р\. Рассматривая цикл V — (&{,..., ёй), мы получаем его п-цикл для каждого п > 1 следующим образом:

= О.

где для каждого возможного г (т.е. i Е {1,,..,(п-1)-г>}) мы считаем, что Щ ~ Причём = р1 . В диссертации кроме определения, также

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

т.

В пространстве состояний строится корневое дерево18 С для поиска состояния, включающее минимально возможное множество блоков

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

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

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

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

где:

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

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

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

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

В дереве <3 ребром а 6 Л будет пара двух вершин V! и Уз, т.е. о = {У:, Уз}) где VI и Ц являются смежными вершинами в дереве С, Вх 6 VI и £ Уг, причём Вг = БД6 (где Ь - блок).

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

Схема алгоритма 2 . Поиск подмножества В множества блоков В, которое содержит минимально возможное множество блоков, все элементы множества бинарного отношения # и множество простых циклов, соответствующих множеству всех простых циклов базисного автомата В4.

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

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

Вход: Множество блоков В, базисный автомат В4.21

Шаг 1: Находим множество всех простых циклов базисного автомата

Шаг 2: Удаляем некоторый блок. Блок, который удаляется, выбирается из

ещё не рассмотренных подмножеств, имеющих минимальное число блоков.22

Получаем подмножество В множества В. Сравниваем подмножество В с

уже рассмотренными подмножествами. Строим новый элемент пространства

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

которые содержатся в подмножестве В, то переходим на шаг 2.

Шаг 3: Строим множество простых циклов подмножества В?3

Шаг 4: Проверяем соответствует ли множество простых циклов подмножества

В множеству всех простых циклов базисного автомата 04. Если

соответствует, то переходим на шаг 2. Причём если соответствует, то

подмножество В может быть текущим псевдооптимальным решением. Если

не соответствует, то помечаем рассматриваемый лист как «неправильный» и

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

решением.

Выход: Подмножество В множества блоков В.24 О

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

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

(ЗА, В 6 Q*) (VX е Q„) (АфХ и В#Х).

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

(ЭХ, У 6 Qp) (VA G Qv) (A#X И A#Y) .

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

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

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

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

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

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

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

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

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

Утверждение 1 . Если в «меньшем» из двух канонических автоматов (для языков L и LR) имеется N состояний, то в «большем» их не более, чем 2* -1. 0

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

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

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

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

2вСм. [Jiang, T. Minimal NFA Problems are Hard / T. Jiang., B. Ravikumar - SIAM J. Comput., V.22, 1993].

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

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

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

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

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

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

2. Мельников, Б.Ф. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов / Б.Ф. Мельников, М.Р. Сайфуллина // Известия высших учебных заведений. Математика. - 2009. - № 4. - С. 67-71. (Имеется английский перевод: Melnikov, В. F. Some algorithms for equivalent transformation of nonde-terministic finite automata / B. P. 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. - С. 69-72.

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

6. Зузанова, М.Р. Алгоритмы и модель для эквивалентного преобразования недетерминированных конечных автоматов / М.Р. Зузанова / / Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», 1-5 декабря 2009 г. - Ульяновск : сбоник научных трудов Т.2, УлГТУ, 2009. - С. 335-340.

Подписано в печать 25.05.2010. Формат 60x84/16. Печать оперативная. Усл. п. л. 1,4. Уч.-изд. л. 1,3. Тираж 120 экз. Заказ № 3-64-10.

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