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

МЕЛЬНИКОВА

Александра Александровна

БАЗИСНЫЙ

КОНЕЧНЫЙ АВТОМАТ

КАК ИНВАРИАНТ

РЕГУЛЯРНОГО ЯЗЫКА

01.01.09 – дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Казань – 2013

Работа выполнена в Димитровградском инженерно-технологическом институте – филиале ФГАОУ ВПО Национальный исследовательский ядерный университет “Московский инженерно-физический институт” на кафедре Высшая математика.

Научный руководитель: доктор физико-математических наук профессор Мельников Борис Феликсович (заведующий кафедрой Прикладная математика и информатика Тольяттинского филиала ФГБОУ ВПО Самарский государственный университет )

Официальные оппоненты: доктор физико-математических наук доцент Захаров Владимир Анатольевич (заведующий лабораторией математических проблем компьютерной безопасности ФГБОУ ВПО Московский государственный университет им. М. В. Ломоносова ) кандидат физико-математических наук доцент Богомолов Алексей Сергеевич (доцент кафедры математической кибернетики и компьютерных наук ФГБОУ ВПО Саратовский государственный университет имени Н. Г. Чернышевского )

Ведущая организация: ФГБОУ ВПО Самарский государственный университет путей сообщения

Защита диссертации состоится 27 декабря 2013 г. в 14:30 часов на заседании диссертационного совета Д 212.081.24 при Казанском (Приволжском) федеральном университете по адресу: г. Казань, ул. Кремлёвская, д. 35, корпус 2, аудитория 1011.

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

Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 420008, г. Казань, ул. Кремлёвская, д. 35, диссертационный совет Д 212.081.24.

Автореферат разослан ноября 2013 г.

Учёный секретарь диссертационного совета Д 212.081.24, кандидат физико-математических наук, доцент Еникеев А.И.

1

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

Актуальность темы. В 1960-х годах активно развивалась теория конечных автоматов Рабина-Скотта, в литературе было очень много соответствующих научных публикаций 1. Но примерно с начала 1970-х годов, с появлением развитой теории детерминированных конечных автоматов, в научных статьях часто стало прослеживаться мнение, что в теории регулярных языков и конечных автоматов уже решены практически все возможные задачи. Когда же данная теория стала применяться к различным вопросам смежных наук, оказалось, что остаётся важным способ, которым задаётся регулярный язык, а не только сам исследуемый язык 2. Именно подобные проблемы приводят к необходимости рассматривать представление регулярных языков с помощью базисных конечных автоматов, которым и посвящена настоящая диссертация. Базисный автомат является инвариантом заданного регулярного языка, альтернативным каноническому автомату. Развиваемая в диссертации теория применяется для решения различных задач теории регулярных языков, а также некоторых задач дискретной оптимизации, причём как точными, так и эвристическими методами.

Недетерминированные конечные автоматы (ниже – НКА), изучаемые в диссертационной работе, впервые рассматривались в середине прошлого века Ю.Медведевым 3, а также М.Рабином и Д.Скоттом 4. Позднее, прежде всего – при применении НКА к решению различных прикладных задач, указанные автоматы модифицировались и обобщались многими авторами 5. Важным обобщением стали недетерминированные автоматыраспознаватели с магазинной памятью (push-down automata, МП-автоматы), появившиеся как одно из средств автоматического перевода, а также для различных целей программирования, широко используемые в теории трансляции 6. Как МП-автоматы, так и НКА служат примером так называемых автоматов-распознавателей – в отличие от конечных автоматов-преобразователей (например, конечных автоматов Мили, Мура), которые в представляемой диссертационной работе не рассматриваются. Конечные автоматы и такие тесно связанные с ними конструкции, как, например, линейные грамматики и регулярные выражения, относятся к основным понятиям информатики.

Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и алгоритмов 7. Эффективность применения именно конечных автоматов 1 Подробные библиографии работ 1960–70-х годов можно найти, например, в следующих монографиях:

• Кудрявцев В., Алёшин С., Подколзин А. Введение в теорию автоматов // М. – Наука. – 1985. – • Иванов Н., Михайлов Г., Руднев В., Таль А. Конечные автоматы: эквивалентность и поведение 2 Sheng Yu. A renaissance of automata theory? // Bulletin of the Eur. Assoc. Theor. Comput. Sci., No.

72. – 2000. – 270–272.

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

4 Rabin M., Scott D. Finite automata and their decision problems // IBM J. Research and Development.

– 1959. – Vol. 3. – 115–125.

5 См., например:

• Гилл А. Линейные последовательностные машины // М. – Наука. – 1974. – 288 с.

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

• Melnikov B. On an expansion of nondeterministic nite automata // Journal of Applied Math. and Computing. – Springer Berlin/Heidelberg. – 2007. – V.24. – No.1-2. – 155–165.

• Твердохлебов В. Геометрические образы законов функционирования автоматов // Саратов:

ООО Издательский Центр Научная книга. – 2008. – 183 с.

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

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

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

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

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

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

Объектом исследования являлись недетерминированные конечные автоматы Рабина-Скотта (Медведева), в первую очередь – определённые автором базисные НКА.

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

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

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

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

8 См. в вышеуказанных монографиях, а также, например, в следующей: Hromkovi J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimazation, Randomization, Approximation, and Heuristics // Springer. – 2003. – 544 p.

9 См., например:

• Hashiguchi K. Algorithms for determining the smallest number of nonterminals (states) sucient for generating (accepting) a regular language // ICALP. – 1991. – 641–648.

• Kameda T., Weiner P. On the state minimization of nondeterministic nite automata // IEEE Trans.

on Computers. – 1970. – C-19. – 617–627.

• Jiang T., Ravikumar B. Minimal NFA Problems are Hard // SIAM J. Comput. – 1993. – V. 22, No. 1.

– 1117–1141.

10 Работы в этом направлении только начались. См.: Крайнюков Н., Мельников Б. Функция разметки состояний и базисные слова для конечных автоматов // Межд. конф. Совр. проблемы математики, информатики и биоинформатики, посвящённая 100-летию А.А.Ляпунова. – 2010. – 65–66.

прежде всего – при решении проблемы дуговой минимизации.

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

Практическая значимость исследования. Полученные результаты могут быть применены при доказательстве теорем, связанных с регулярными языками и недетерминированными конечными автоматами, а также при описании алгоритмов эквивалентного преобразования конечных автоматов 11, в том числе – при построении автоматов, эквивалентных заданному 12, Кроме того, результаты диссертации могут быть применены в различных задачах минимизации недетерминированных конечных автоматов – в вершинной 13, дуговой ([18]) и т.н. звёздно-высотной минимизации 14, а также минимизации по некоторым комбинированным критериям. Для каждой из этих задач может помочь построение т.н. универсального автомата Конвэя – которое также удатся выполнить на основе базисного автомата 15. При этом результаты диссертации (прежде всего – результаты главы 5) могут быть применены и для создания эвристических алгоритмов решения перечисленных задач дискретной оптимизации 16. Результаты представляемой диссертации применяются также в смежных областях – а именно, для проверки репрезентативности случайно сгенерированных дискретных структур и описания специальных подходов к кластеризации 17 и для описания специальных математических моделей 18.

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

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

12 Например, схожие конструкции были применены в следующей статье, опубликованной через лет после статьи [17] соискателя данной диссертации: van Glabbeek R., Ploeger B. Five determinisation algorithms // In: O.Ibarra and B.Ravikumar, editors. Implementation and Applications of Automata. – Springer, LNCS. – 2008. – V.5148. – 161–170.

13 См., например:

• статьи, указанные в двух предыдущих сносках;

• следующую диссертацию: Зузанова М. Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов // Дисс.... канд. физ.-мат. наук: 05.13.18, Тольяттинский государственный университет, Д 212.264.03, защищена 01.07.10;

• а также цитируемые ниже статьи, выполненые под рук. Цыганова.

14 Баумгертнер С., Мельников Б. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов // Вестник Воронежского государственного университета, Системы управления и информационные технологии. – 2010. – №1. – 5–7.

15 Мельников Б., Зубова М. Построение автомата COM на основе базисного автомата // Вектор науки Тольяттинского государственного университета. – 2010. – №4. – 30–32.

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

• Цыганов А., Булычов О. HeO: библиотека метаэвристик для задач дискретной оптимизации // Программные продукты и системы. – 2009. – №4. – 148–151.

• Цыганов А., Булычов О. Параллельные эвристические алгоритмы для задачи вершинной минимизации недетерминированных конечных автоматов // Вестник Воронежского государственного университета, Системы управления и информационные технологии. – 2010. – №1. – 60–63.

17 Мельников Б., Пивнева С., Рогова О. Репрезентативность случайно сгенерированных конечных автоматов с точки зрения базисных автоматов // Стохастическая оптимизация в информатике (изд-во СПбГУ). – 2010. – Том 6. – 74–82.

18 Также см. вышеуказанную диссертацию Зузановой.

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

• Определение функций разметки состояний заданного конечного автомата.

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

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

• Формулировка свойств базисного конечного автомата:

– эквивалентность базисного автомата и канонического;

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

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

– утверждения о свойствах таблицы состояний конечного автомата;

– утверждения о свойствах функций разметки.

Доказательство соответствующих утверждений о свойствах базисного автомата.

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

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

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

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

• Международная алгебраическая конференция памяти А.Г.Куроша, Москва, МГУ, • VII Международный семинар Дискретная математика и её приложения, Москва, МГУ, 2001 г.

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

• Научный семинар для аспирантов кафедры МАТИС (под руководством д.ф.-м.н.

В.Буевича и С.Алёшина), Москва, МГУ, 2001 и 2002 г.г.

• Научный семинар (под руководством д.ф.-м.н. Г.Осипова), Переславль-Залесский, ИПСРАН, 2001 и 2003 г.г.

• XIII Международная конференция Проблемы теоретической кибернетики, Казань, 2002 г.

• Международная научно-практическая конференция Проблемы математического образования и культуры, Тольятти, ТГУ, 2003 г.

• Международная конференция Общие проблемы управления и их приложения.

Проблемы преподавания математики Тамбов, ТГУ, 2007 и 2009 г.г.

• Научный семинар по математической кибернетике и дискретной математике при Диссертационном совете Д 212.081.24, Казань, КГУ (КПФУ), 2009, 2011 и 2013 г.г.

• Научный семинар кафедры математического анализа Ульяновского государственного педагогического университета, 2010 и 2012 г.г.

• Научный семинар по дискретной математике, Димитровград, Филиал УлГУ и ДИТИ – филиал НИЯУ Московский инженерно-физический институт, 1999– Публикации. Основные результаты диссертации опубликованы в 20 работах, 7 из которых входят в список изданий, рекомендованных ВАК. Список работ приведён в конце автореферата.

Личный вклад. Изложенные утверждения и теоремы доказаны лично автором, либо совместно с научным руководителем. Результаты, полученные в совместных с научным руководителем работах [1, 5, 6, 8, 14, 16, 18, 19], принадлежат в части, касающейся базисных автоматов, автору диссертации.

Структура и объём диссертации. Общий объём диссертационной работы – 102 страницы 14-го кегля. Диссертация состоит из 5 глав (включая введение и заключение) и списка используемой литературы из 106 наименований. В тексте диссертации содержатся 31 рисунок и 26 таблиц.

2 Содержание работы Глава 1 ( Введение ) В главе 1 формулируются цели и задачи работы, даётся краткий исторический обзор, освещается актуальность и новизна исследуемой темы, конкретизируется предмет исследования – недетерминированный конечный автомат Рабина-Скотта (Медведева) для некоторого заданного регулярного языка L, говорится о различных способах задания автомата. В работе в первую очередь применяется задание НКА для некоторого регулярного языка L пятёркой вида K = ( Q,,, S, F ), где:

• Q – некоторое конечное множество состояний (вершин);

• – рассматриваемый алфавит (автомат K вводится для задания языка L над этим алфавитом);

• – функция переходов вида : Q ( {}) P(Q), (где – пустое слово, P – множество всех подмножеств данного множества);

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

• F Q – множество финальных состояний (выходов).

В работе используется также функция переходов вида : QQ P({}), такая что для некоторой пары состояний q1, q2 Q и некоторой буквы a условие (q1, q2 ) a считается выполненным при (q1, a) q2. Вводится определение зеркального к K конечного автомата K R = ( Q,, R, F, S ), для которого R (q1, a) q2 выполнено тогда и только тогда, когда (q2, a) q1. Автомат K R задаёт зеркальный (инверсный) к L язык LR.

Через Lin (q) и Lout (q) обозначаются входной и выходной языки состояния q, т.е.

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

• {q1, q2 } {q3, q4 }, если для некоторого a, имеем (q1, a) = {q3 } и (q2, a) = • {q1, q2 } F, если из двух состояний q1, q2 ровно одно финальное.

Рассмотрим + – транзитивное замыкание отношения. При этом Lout (q1 ) = Lout (q2 ) тогда и только тогда, когда не выполнено условие {q1, q2 } + F. Если выходные языки состояний q1 и q2 равны (т.е. эти состояния эквивалентны), то можно объединить эти состояния (при этом мы без ограничения общности считаем, что q2 – не вход):

• для всех вершин r Q множество дуг (r, q1 ) заменяем на множество (r, q1 ) • удаляем q2 и все дуги множеств (r, q2 ) и (q2, r).

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

K будет всюду определённым, если добавить (при необходимости) одно бесполезное состояние N.

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

Глава 2 ( Базисные конечные автоматы – определения, примеры и алгоритмы построения ) Во 2-й главе определяется новый объект в теории конечных автоматов Рабина-Скотта – так называемый базисный автомат для заданного регулярного языка L. Этот автомат является единственным для данного языка L, причём является его инвариантом.

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

В разделе 2.1 рассматриваются дополнительные определения, необходимые для введения понятия базисного автомата. А именно, определяется бинарное отношение # на множестве пар состояний двух канонических автоматов – для заданного языка L и для инверсного языка LR.

Для произвольного НКА 19 Всюду определённый (total) автомат определяется согласно следующей монографии: Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции // М. – Мир. – 1978. – Т. 1.

обозначим через L(K) язык, определяемый K. Регулярный язык L первоначально задаётся некоторым автоматом K, т.е. L = L(K).

Автомат – эквивалентный автомат в канонической форме, единственный с точностью до переобозначения состояний, а автомат в канонической форме, определяющий зеркальный к L язык LR.

Бинарное отношение # определяется следующим образом:

A#X тогда и только тогда, когда где # Q R, а Q и R – множества состояний автоматов в канонической форме L и LR соответственно. Очевидно, что существуют несложные алгоритмы построения этого бинарного отношения, т.е. приведённое определение конструктивно.

В разделе 2.2 приводится основное введённое автором определение – определение базисного автомата.

Определение 1 Автомат над некоторым алфавитом для следующих множеств T, T, ST и FT :

• T = {(A, X) | для любого A Q, X R, A#X} (обозначим A как (T ), X как • T ST если и только если (T ) = sQ (это означает, что (T ) – единственное начальное состояние L, т.е. sQ );

• T FT если и только если (T ) = sR (это означает, что (T ) – единственное начальное состояние автомата LR, т.е. sR ) назовём базисным автоматом для данного языка L и обозначим через BA(L).

Это определение конструктивно – в том смысле, что является также алгоритмом построения базисного автомата, аналогично определению бинарного отношения #. Существуют и альтернативные способы построения базисного автомата – см. ниже, в разделе 2.9 представляемой диссертации. Отметим, что для заданного регулярного языка L, в соответствие с определением, строится единственный базисный автомат BA(L).

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

Для заданного регулярного языка L рассмотрим определяющий его произвольный НКА K, а также произвольный всюду определённый автомат (по определению являющийся детерминированным) Для этой пары автоматов K и Z in : Q P(QZ ) является полной функцией разметки (в дальнейшем, для краткости, функцией разметки), если для каждых q Q и q QZ множество in (q) содержит q в том и только том случае, если Последнее определение можно считать и алгоритмом построения функции in, поKZ скольку Lin (q) и Lin (q) – регулярные языки. Отметим, что в процессе построения эквивалентного канонического автомата, выполненного специальным образом, можно получить и более простой алгоритм построения этой функции, что используется в примерах раздела 2.8 данной диссертации.

В разделе 2.4 рассмотрен подробный пример построения базисного автомата для языка, заданного регулярным выражением (a + ab + ba). Граф переходов автомата K, одного из НКA, задающих данный регулярный язык, показан на рис. 1. Изменив на этом рисунке направления стрелок на противоположные, получим граф переходов зеркального к K автомата K R, задающего инверсный язык LR.

Соответствующий конечный автомат в канонической форме – L. Графы переходов автоматов L и LR приведены на рис. 2 и рис. 3.

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

Несложно доказывается, что для бесполезных состояний канонических автоматов не может выполняться ни N #X, ни A#N для любых состояний A, X этих автоматов, поэтому бесполезное состояние не может входить в состояние базисного автомата. В графах переходов канонических автоматов бесполезные состояния для удобства также не указываются. Это делает граф более наглядным.

В рассматриваемом нами примере из равенства L = LR следует, что графы переходов автоматов L и LR совпадают. Состояния автомата LR обозначены через X, Y и Z (вместо A, B и C).

При этом прямая и обратная функции разметки имеют значения:

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

таким образом мы получаем значения прямой функции разметки.

Для получения значений обратной функции разметки (out (q) = inR (q) ) можно считать, что:

и так далее, в силу L = LR.

Отношение # может быть задано 20 следующей таблицей 1:

По определению автомата BA(L), и BA(L) может быть определён следующей таблицей:

где стартовые состояния помечены символом, а финальные – символом.

Не останавливаясь подробно на всём процессе построения этой таблицы, рассмотрим только состояние (B, X). Оно не является начальным, так как ((B, X)) = B – не начальное состояние автомата L. Но (B, X) является финальным в силу того, что ((B, X)) = X – начальное состояние LR. Состояние (B, X) имеет две исходящих дуги, а именно:

• в состояние (B, Z), помеченная a, так как L имеет дугу из B в B, помеченную a, и LR имеет дугу из Z в X, помеченную также a;

• в состояние (A, Y ), помеченная b, так как L имеет дугу из B в A, помеченную b, и LR имеет дугу из Y в X, помеченную также b.

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

20 Сам алгоритм построения отношения # описан, например, в следующей статье: Melnikov B. A new algorithm of the state-minimization for the nondeterministic nite automata // The Korean J. of Comp.

and App. Math. – V. 6. – No. 2. – 1999. – 277–290.

Таким образом нами построен базисный автомат, задающий регулярный язык, определяемый регулярным выражением (a + ab + ba). Этот пример используется в работе и далее.

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

Утверждение В разделе 2.6 доказывается однозначность базисного автомата 21, т. е. единственность последовательности его состояний при принятии им некоторого слова, принадлежащего рассматриваемому регулярному языку. Произвольный недетерминированный конечный автомат, читая слово, проходит последовательность состояний. Если такая последовательность единственна, то соответствующий автомат называется, аналогично другим подобным случаям в теории формальных языков, однозначным (unambiguous).

В противном случае, когда некоторому слову языка автомата соответствует две или более последовательности состояний, – неоднозначным (ambiguous). Однозначные автоматы могут быть удобнее при использовании для решения различных проблем. Например, существует аналогия между последовательностью подмножеств контекстносвободных языков, а значит соответствующих магазинных (push-down) автоматов, и следующей последовательностью подмножеств множества конечных автоматов: произвольные автоматы, однозначные автоматы, детерминированные автоматы, автоматы в канонической форме.

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

Утверждение 2 Базисный автомат для данного регулярного языка является однозначным.

Эквивалентная формулировка этого утверждения такова.

Каждое слово языка автомата BA(L) определяет единственную Утверждение последовательность состояний BA(L).

В разделе 2.7 доказывается cвойство допускающего пути любого автомата для заданного регулярного языка, т.е. свойство автомата BA(L), связывающее его с произвольным автоматом K, допускающим рассматриваемый регулярный язык.

Предположим, что слово u принадлежит языку L и число букв u равно n.

21 Про однозначные и неоднозначные автоматы см., например, в следующей статье: Мельников Б.

Однозначные конечные автоматы // Известия ВУЗов. Cерия Технические науки (Поволжский регион). – 2002. – №2. Важно отметить, что сформулированные в ней критерии однозначности используют функции разметки состояний, и, следовательно, напрямую связаны с вопросами, рассматриваемыми в данной диссертации.

Рассмотрим единственную последовательность состояний автомата B A(L), такую что B A(L) читает буквы слова u и проходит свои состояния в следующем порядке:

(A0, X0 ), (A1, X1 ), (A2, X2 ),..., (An, Xn ).

Рассмотрим также одну из последовательностей состояний, которые проходит автомат K при чтении слова u (для простоты будем рассматривать автоматы без переходов):

Указанные свойства связывают базисный автомат с любым недетерминированным автоматом K, допускающим рассматриваемый регулярный язык, следующим образом:

базисный автомат моделирует работу автомата K. Эти свойства делают новый автомат более удобным для использования в некоторых специальных задачах, связанных с теорией регулярных языков, что указано в разделе 1.1 представляемой диссертации и подробно показано в главах, следующих за данной главой 22. Можно сказать, что примеры выполнения этих свойств нами приведены на основе автомата, рассмотренного ранее (в разделе 2.4).

В разделе 2.8 рассматриваются ещё два примера построения базисного автомата.

Эти примеры демонстрируют выполнение свойств, описанных в предыдущих разделах.

В разделе 2.9 приведён альтернативный алгоритм построения дуг базисного автомата. Кратко опишем его, применяя следующие обозначения. Дуги автоматов L и LR будем обозначать заглавными греческими буквами, не совпадающими по написанию с латинскими – до буквы для автомата L и начиная с буквы для автомата LR, а также для зеркального к последнему автомата (LR )R. Для некоторой конкретной дуги, идущей из вершины A в вершину B и имеющей пометку a, будем писать a () = A Выберем некоторую букву a ; описанную здесь процедуру мы проделаем для каждой буквы алфавита. Пусть Q – помеченные буквой a дуги автомата L (т.е. элеa менты множества Q ), а R – помеченые буквой a дуги автомата LR (т.е. элементы множества R ). Аналогично сказанному выше, будем таким же образом обозначать соответствующее множество дуг автомата (LR )R.

Рассмотрим бинарное отношение #a Q R, определённое следующим образом.

Для некоторых Q и R полагаем #a тогда и только тогда, когда для некоторого слова w L имеем представление w = uav, и при этом:

Приведённое определение отношения #a с помощью (5) можно рассматривать как алгоритм его построения.

Утверждение 5 Пусть Q и R – некоторые дуги канонических автоматов для языков L и LR соответственно. Тогда в базисном автомате BA(L) имеется дуга 22 Ранее эти свойства нашли применение в различных работах, связанных с алгоритмами эквивалентного преобразования НКА, – см., например, практически все публикации автора представляемой диссертации. А среди последних вариантов применения можно отметить следующие статьи:

• Melnikov B. On an expansion of nondeterministic nite automata // J. of Applied Mathematics and Computing, Springer Berlin/Heidelberg. – Vol. 24, No. 1–2. – 2007. – 155–165.

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

тогда и только тогда, когда #a.

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

В разделе 3.1 формулируются и доказываются некоторые используемые далее в работе свойства функции разметки 23.

Утверждение Утверждение Утверждение В разделе 3.2 приводится вариант объединения тех состояний недетерминированного автомата (1), которые имеют одинаковые значения функций in или out. Это делается аналогично тому, как два эквивалентных состояния могут быть объединены в случае детерминированных автоматов.

Определение 2 Для некоторой пары состояний НКА (1), т.е. для q1, q2 Q, определим автомат J q1 q2 (K), граф переходов которого получается из графа переходов автомата K следующим образом.

• Для каждого состояния r Q, соответствующее множество дуг (q1, r) заменяется на множество (q1, r) (q2, r).

• Аналогично, для каждого состояния r Q, множество дуг (r, q1 ) заменяется на множество (r, q1 ) (r, q2 ). • Состояние q2 отбрасывается; соответствующие элементы функции переходов также отбрасываются.

23 Они были приведены без доказательств в статье Melnikov B. A new algorithm of the state-minimization for the nondeterministic nite automata // The Korean J. of Comp. and App. Math. – 1999. – V. 6.

– No. 2. – 277–290. В представляемой диссертации приводятся соответствующие доказательства.

24 Поэтому, если имеются какие-либо из следующих четырёх случаев: q, q {q, q }, тогда каждая дуга (q, q ) a заменяется на петлю (q1, q1 ) a.

Кроме того, состояние q1 автомата J q1 q2 (K) – стартовое (финальное) тогда и только тогда, когда по крайней мере одно из состояний q1, q2 является стартовым (финальным) в автомате K.

Утверждения 10 и 11 (см. [19]) определяют первый алгоритм объединения состояний 25.

Утверждение 10 Пусть для автомата (1) и некоторых его состояний q1, q2 Q выполнено равенство:

Тогда для автомата K1 = J q1 q2 (K) выполняется следующее равенство:

Кроме того, Утверждение 11 Пусть для автомата (1) и некоторых его состояний q1, q2 Q выполнено следующее равенство:

Тогда для автомата K1 = J q1 q2 (K) выполняется равенство Далее, в разделе 3.3, приведены примеры применения алгоритма объединения состояний недетерминированного автомата.

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

Доказано, что канонический автомат LR содержит не более 2n 1 состояний (где n – число состояний автомата L) 26. Этим же числом ограничивается число возможных столбцов таблицы отношения #, в которой n строк. Кроме того, доказано, что в таблице соответствия состояний не может быть одинаковых строк и столбцов.

Следующие утверждения 12–15 доказываются на основе определения базисного автомата.

Утверждение 12 Пусть задан регулярный язык L, его канонический автомат L и некоторое состояние A автомата L. Тогда для каждого состояния X автомата LR выполнено следующее:

25 Аналогично утверждениям 6 и 8, эти утверждения были приведены без доказательств в статье [19]. Доказательства были впоследствии опубликованы в следующей статье: Melnikov B. Once more on the edge-minimization of nondeterministic nite automata and the connected problems // Fundamenta Informaticae – 2010. – V. 104. – No. 3. – 267–283. В представляемой диссертации соответствующие доказательства не рассматриваются – однако рассматриваются примеры применения, связанные с основным объектом диссертации – базисными конечными автоматами.

26 В представляемой диссертации приведено более полное доказательство, чем доказательство, приведённое в вышеупомянутой диссертации Зузановой. То же самое относится к ещё двум утверждениям разделов 3.4 и 3.5.

Утверждение 13 Пусть задан регулярный язык L, канонический для LR автомат (LR )R, и X – некоторое состояние LR. 27 Тогда для каждого состояния A автомата L выполнено следующее:

Далее, как и выше, применяются обозначения (в частности – Q и R), введённые ранее в (2) и (3).

Утверждение 14 Пусть задан регулярный язык L и его канонический автомат L.

Тогда для некоторого состояния A автомата L выполнено следующее:

Утверждение 15 Пусть задан регулярный язык L, и LR – канонический автомат, определяющий LR. Тогда для некоторого состояния X автомата LR выполнено следующее:

Утверждение 16 Пусть канонический автомат L для данного регулярного языка L имеет по крайней мере два различных состояния 28, и A, B – некоторая пара таких состояний. Тогда существует состояние X канонического автомата LR, такое что базисный автомат для языка L содержит в точности одно состояние из следующих двух: (A, X) и (B, X).

Утверждение 17 Пусть канонический автомат LR, определяющий язык LR, имеет по крайней мере 2 различных состояния, и X, Y – некоторая пара таких состояний.

Тогда существует состояние A канонического автомата L, такое что базисный автомат для L содержит ровно 1 состояние из следующих: (A, X) и (A, Y ).

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

Глава 4 ( Применение базисных автоматов в задачах минимизации недетерминированных конечных автоматов ) 4-я глава посвящена применению базисных автоматов в различных задачах минимизации недетерминированных конечных автоматов, в первую очередь – в точных (не эвристических) алгоритмах.

В разделе 4.1 определяются специальные объекты, также связанные с базисными автоматами. Это – блоки и псевдоблоки, состоящие из пары множеств вершин. Блоки и псевдоблоки используются в дальнейших построениях (во всех разделах 4-й и 5-й глав), определения иллюстрируются примерами.

27 Поэтому X может также рассматриваться как состояние автомата (LR )R.

28 Как и ранее, возможное бесполезное состояние канонического автомата не рассматриваем.

Определение 3 Пара непустых подмножеств Q Q и R R образует псевдоблок, если выполняется следующее условие: (A Q, X R) (A#X).

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

При этом здесь, как и ранее, не будет рассматриваться бесполезное состояние N, так как согласно вышеизложенному ни одно из рассматриваемых подмножеств состояний (Q и R) не может его содержать. Кроме того, очевидно, что множество блоков является подмножеством множества псевдоблоков.

Для каждого псевдоблока B через (B) обозначим соответствующие ему состояния Q Q, а через (B) – соответствующие состояния R R. При этом будем также обозначать данный псевдоблок записью B(Q, R).

Также в разделе 4.1 формулируется необходимое условие минимальности автомата по числу вершин 29. Это условие было получено на основе развитой автором представляемой диссертации теории базисных автоматов и может рассматриваться как одно из приложений этой теории.

Определение 4 Пусть B1 и B2 – некоторые псевдоблоки. Будем говорить, что B покрывает B1, если Определение 5 Назовём некоторое множество псевдоблоков полным, если для каждого элемента T Q R существует некоторый псевдоблок B этого множества, такой что T B. Необходимое условие минимальности автомата по числу вершин заключается в том, что множество его вершин образует полное множество псевдоблоков. При таком множестве блоков (т.е. при выполнении этого необходимого условия) имеется следующая формулировка достаточного условия минимальности автомата по числу вершин: его множество дуг включает все возможные дуги, удовлетворяющие ограничениям, сформулированным в следующем разделе 4.2.

Возможные дуги конечного автомата для заданного регулярного языка рассматриваются в разделе 4.2. Множество возможных дуг любого недетерминированного конечного автомата, определяющего заданный регулярный язык, описывается на множестве псевдоблоков (вместо вершин заданного автомата) 31. Описанное множество возможных дуг применяется к следующей проблеме, рассматриваемой в данной главе диссертации, – проблеме дуговой минимизации.

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

• Melnikov B. A new algorithm of the state-minimization for the nondeterministic nite automata. – The Korean Journal of Computational and Applied Mathematics. – Vol. 6, No. 2. – 1999. – 277–290.

• Melnikov B. Once more about the state-minimization of the nondeterministic nite automata. – The Korean Journal of Computational and Applied Mathematics. – Vol. 7, No. 3. – 2000. – 655–662.

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

31 Подробнее см. следующую статью: Melnikov B., Sciarini-Guryanova N. Possible edges of a nite automaton dening the given regular language // The Korean J. of Comp. and App. Math. – V. 9. – No. 2.

– 2002. – 475–485.

удобны при решении различных практических задач, возникающих в теории регулярных языков 32.

Алгоритм Вход: заданный регулярный язык L.

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

Метод.

• Зафиксировать некоторое множество псевдоблоков на множестве Q R. При этом можно считать, что выполняются следующие два условия (т.е. выбирать только такие множества псевдоблоков, которые удовлетворяют им обоим) 33 :

1) это множество является полным;

2) ни один из псевдоблоков множества не покрывает никакой другой 34.

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

• Определить множество возможных дуг между вершинами (пусть M).

• Перебрав все возможные множества псевдоблоков (удовлетворяющих сформулированным выше условиям), а для каждого из таких множеств – все подмножества построенного нами множества M, определить те из них, при которых полученный автомат:

– действительно определяет язык L;

– имеет минимально возможное число дуг.

Также в разделе 4.3 приводятся соответствующие примеры.

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

Алгоритм Вход: заданный регулярный язык L.

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

Метод.

• Построить множество блоков.

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

• Построить множество дуг следующим образом. Для некоторых двух вершин q1 и q2 (допускаем возможность q1 = q2 ) и некоторой буквы a считаем 32 Алгоритмы этого и следующего разделов приведены в статье [18] соискателя данной диссертации.

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

33 Заранее отметим, что множество блоков, рассматриваемых как псевдоблоки, этим условиям удовлетворяет.

34 В том числе – нет двух псевдоблоков с одинаковыми значениями либо.

базисном автомате существует дуга • Перебирая подмножества множества, определить то из них (искомое множество ), при котором полученный автомат:

– действительно определяет язык L;

– имеет минимально возможное число дуг.

Глава 5 ( Заключение ) В заключении работы приводятся её основные результаты.

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

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

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

• Исследованы свойства базисного конечного автомата:

– доказана эквивалентность базисного автомата и канонического;

– доказана однозначность базисного автомата;

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

– доказаны утверждения о свойствах таблицы состояний конечного автомата;

– доказаны утверждения о свойствах функций разметки.

• Доказанные свойства базисного автомата применены для описания новых вариантов алгоритмов вершинной минимизации НКА – причём как точных, так и псевдооптимальных алгоритмов реального времени.

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

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

Подробнее см. процитированную выше диссертацию Зузановой.

Список литературы [1] Melnikov B., Melnikova A. A new algorithm of constructing the basis nite automaton // Informatika (Lithuania). – Vol. 13. – No. 3. – Lithuania. – 2002. – 299–310. (Рецензируемый журнал, рекомендованный ВАК.) [2] Мельникова А.А. Базисные автоматы в решении проблемы оптимизации // Вестник Тамбовского университета. Сер. Естественные и техн. науки. – Т. 12. – Вып. 4.

– Тамбов: Изд-во ТГУ. – 2007. – 492–494. (Рецензируемый журнал, рекомендованный ВАК.) [3] Мельникова А.А. Применение свойств конечных автоматов в алгоритмах вершинной минимизации // Вестник Тамбовского университета. Сер. Естественные и техн. науки. – Т. 14. – Вып.4. – Тамбов: Изд-во ТГУ. – 2009. – 763–765. (Рецензируемый журнал, рекомендованный ВАК.) [4] Мельникова А.А. К вопросу о сходимости значений динамических функций риска // Вестник транспорта Поволжья. – Т. 24. – Вып.4. – Самара: Изд-во СамГУПС.

– 2010. – 11–15. (Рецензируемый журнал, рекомендованный ВАК.) [5] Мельников Б.Ф., Мельникова А.А. Многоаспектная минимизация недетерминированных конечных автоматов. Часть I. Вспомогательные факты и алгоритмы // Известия вузов. Поволжский регион. Физико-математические науки. – № 4 (20).

– 2011. – 59–69. (Рецензируемый журнал, рекомендованный ВАК.) [6] Мельников Б.Ф., Мельникова А.А. Многоаспектная минимизация недетерминированных конечных автоматов. Часть II. Основные алгоритмы // Известия вузов. Поволжский регион. Физико-математические науки. – № 1 (21). – 2012. – 31–43.

(Рецензируемый журнал, рекомендованный ВАК.) [7] Мельникова А.А. Некоторые свойства базисного автомата // Вестник Воронежского государственного университета. Серия Физика. Математика. – № 2. – 2012.

– 184–189. (Рецензируемый журнал, рекомендованный ВАК.) [8] Мельников Б.Ф., Вахитова А.А. Звёздная высота конечного автомата // Учёные записки УлГУ. Фундаментальные проблемы математики и механики. – Вып.3. – Ульяновск:

Изд-во УлГУ. – 1997. – 51–57.

[9] Вахитова А.А. Базисный конечный автомат Рабина-Скотта как инвариант регулярного языка // Труды научн. конф. Математическое моделирование физических, экономических, социальных систем и процессов. – Ульяновск: Изд-во УлГУ. – 1998. – 13–14.

[10] Вахитова А.А. Об одном алгоритме построения функции разметки конечного автомата // Тезисы докладов Международной алгебраической конференции памяти А.Г. Куроша – М. – Изд-во МГУ. – 1998. – 152–154.

[11] Мельникова А.А. Свойства базисных конечных автоматов // Труды второй научн. конф.

Математическое моделирование физических, экономических, социальных систем и процессов. – Ульяновск: Изд-во УлГУ. – 1999. – С. 11.

[12] Мельникова А.А. Базисные конечные автоматы Рабина-Скотта // Материалы VII международного семинара Дискретная математика и её приложения. Часть II – М. – Изд-во МГУ. – 2001. – 170–172.

[13] Мельникова А.А. Cвойства базисных конечных автоматов как инварианта регулярного языка // Тезисы докладов Межд. научно-практ. конф. Методы и алгоритмы прикладной математики в технике, медицине и экономике – Новочеркасск: Изд-во ЮРГТУ (НПИ).

[14] Мельников Б.Ф., Мельникова А.А. Новый алгоритм построения базисных конечных автоматов // Тезисы докла-дов XIII Межд. конф. Проблемы теоретической кибернетики – М. – Изд-во МГУ. – 2002. – С.124.

[15] Мельникова А.А. Варианты некоторых вспомогательных функций для эвристических алгоритмов // Материалы межд. науч.-практ. конф. Проблемы математического образования и культуры – Тольятти: Изд-во ТГУ. – 2004. – 132–135.

[16] Melnikov B., Vakhitova A. Some more on the nite automata // The Korean Journal of Computational and Applied Mathematics. – Vol. 5. – No. 3. – Korea. – 1998. – 495–506.

[17] Vakhitova A. The basis automaton for the given regular language // The Korean Journal of Computational and Applied Mathematics. – Vol. 6. – No. 3. – Korea. – 1999. – 617–624.

[18] Melnikov B., Melnikova A. Edge-minimization of non-deterministic nite automata // The Korean Journal of Computational and Applied Mathematics. – Vol. 8. – No. 3. – Korea. – 2001. – 469–479.

[19] Melnikov B., Melnikova A. Some propertis of the basis nite automaton // The Korean Journal of Computational and Applied Mathematics. – Vol. 9. – No. 1. – Korea. – 2002. – 135–150.

[20] Мельникова А. Пример использования базисных конечных автоматов // Развитие и перспективы вузовской науки и образования в современных условиях. Сборник научных статей: в 2-х частях. -– 1 часть. -– Димитровград: ДИТИ. – 2012. – 110–114.