Базисные конечные автоматы и их применение в задачах исследования регулярных языков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Мельникова Александра Александровна

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

Специальность 01.01.09 - дискретная математика и математическая кибернетика

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

1 5 НДР

Казань -2012

005014674

005014674

Работа выполнена в Димитровградском инженерно-технологическом институте -филиале Национального исследовательского ядерного университета «Московский инженерно-физический институт» на кафедре «Высшая математика».

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

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

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

профессор, зав. кафедрой АиДМ Волков Михаил Владимирович (Уральский федеральный университет им. первого Президента России Б.Н.Ельцина)

кандидат физико-математических наук Вылиток Алексей Александрович (Московский государственный университет)

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

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

Защита диссертации состоится 29 марта 2012 г. в 17:30 часов на заседании

диссертационного совета Д 212.081.24 при ФГАОУВПО «Казанский

(Приволжский) федеральный университет» по адресу. 420008, г. Казань, ул.

Кремлёвская, д. 35, конференц-зал научной библиотеки им. Н.И. Лобачевского.

С диссертацией можно ознакомиться в научной библиотеке ФГАОУВПО

«Казанский (Приволжский) федеральный университет».

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

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

диссертационного совета Д 212.081.24 при КФУ, /

кандидат физико-математических наук, доцент / ~~ Еникеев А.И

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

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

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

1 Подробные библиографии работ 1900-70-х годов можно найти, например, в следующих монографиях:

• Кудрявцев В., Алешин С., Подколзин Л. Введение в теорию автиматов // М. - Наука. - 1985. - .419 и.

• Иванов Н., Михайлов Г., Руднев В., Таль А. Конечные автоматы: эквивалентность и поведение // М. -Наука. - 1984. - 192 с.

2 Sheng Yu. A renaù.mnce of automata theory4 // Bulletin of the Eur. Assoc.. Theor. Comput. Sei., 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 См., например:

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

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

• Melnikov В. On an expansion of nondeterministic finite automata /'/ Journal of Applied Math, and Computing. - Springer Berlin/Heidelberg. - 2007. - V.24. - No.1-2. - 155-165.

• Твердихлебов В. Геометрические образы законов функционирования автоматов // Саратов: ООО Издательский Центр «Научпая книга». - 2008. - 183 с.

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

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

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

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

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

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

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

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

• Hashigudii К. Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language j/ ICALP. - 1991. - 641-648.

• KamedaT., Werner P. On the state minimization of nondettrministic finite automata // IEEE Trans, on Computers. - 1970. - C-19. - 617-627.

• JiangT., RavikumarB. Minimal NFA Problems are Hard // SIAM J. Comput. - 1993. - V.22, No.l. -1117-1141.

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

и исследованных автором базисных конечных автоматов.

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

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

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

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

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

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

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

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

12 Например, схожие конструкции были применены в следующей статье, опубликованной через 9 лет после статьи |14] соискателя данной диссертации: van GlabbeckR., PloegcrB. Five dclcrminisation algorithms j/ Гп: O.Ibarra and B.Ravikumar, editors. Implementation and Applications of Automata. - Springer, LNCS. - 2008. -V.5148. - 101-170.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Цыганов А., Булычов О. Параллельные эвристические алгоритмы для задачи вершинной минимизации недетерминированных конечных автоматов // Вестник Воронежского государственного университета, «Системы управления и информационные технологии». — 2010. - Д*!1. — 00-03.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Научный семинар для аспирантов кафедры МАТИС (под руководством д.ф.-м.н. В.Буевича и С.Алёшина), Москва, МГУ, 2001 и 2002 г.г.

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

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

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

• Международная конференция «Общие, проблемы управления и их приложения. Проблемы преподавания математики» Тамбов, ТГУ, 2007 и 2009 г.г.

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

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

• Научный семинар по дискретной математике, Димитровград, Филиал УлГУ и ДИТИ - филиал НИЯУ «Московский инженерно-физический институт», 1999-2011 г.г.

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

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

Структура и объём диссертации. Общий объём диссертационной работы -116 страниц 14-го кегля. Диссертация состоит из 6 глав (включая введение и заключение) и списка используемой литературы из 124 наименований. В тексте диссертации содержатся 28 рисунков и 21 таблица.

2 Содержание работы Глава 1 («Введение»)

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

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

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

• 5 - функция переходов вида S : Q х (Е U {е}) —> V(Q), (где в - пустое слово, V ~ множество всех подмножеств данного множества);

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

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

В работе используется также функция переходов вида 7 : Q х Q —+ U {е}). такая что для некоторой пары состояний qy, 92 € Q и некоторой буквы а € Е условие 7(91,52) Э а считается выполненным при 5(qitа) Э 92■ Вводится определение зеркального к К конечного автомата KR = (Q, Е. SR, F,S), для которого 5я(qi, а) Э q-i выполнено тогда и только тогда, когда ¿(92,(1) Э qi -Автомат Кн задаёт зеркальный (инверсный) к L язык

Через C™(q) и £,0к1(ц) обозначаются входной и выходной языки состояния 9, т.е. языки, определяемые автоматами

(Q.EAS.fo}) .1 (Q,S,5,{g},F)

соответственно. А именно, после получения детермннироваипого всюду определённого автомата19

на основе некоторого недетерминированного автомата К, рассмотрим на множестве, содержащем все неупорядоченные пары различных элементов Q, а также специальный элемент Т, следующее бинарное отношение >-:

• {9ьф} >- {53,94}, если для некоторого а € Е, имеем 6(qi,a) — {93} и

¿(?2,а) = {94}-

• {91,92} F, если из двух состояний 91,92 ровно одно финальное.

Рассмотрим - транзитивное замыкание отношения >-. При этом £^"'(91) = C<^t{q2) тогда и только тогда, когда не выполнено условие {91,92} >-+ Т. Если выходные языки состояний 9i и 92 равны (т.е. эти состояния эквивалентны), то можно объединить эти состояния (при этом мы без ограничения общности считаем, что 92 - не вход):

• для всех вершин г € Q множество дуг 7(7-, 91) заменяем на множество 7(r, 9i) U -у (г, 92)

• удаляем 92 и все дуги множеств 7(^,92) и 7(92,г).

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

Задающий язык Ь канонический автомат Ь, единственный с точностью до переобозначения состояний, получается из К объединением всех пар эквивалентных состояний. К будет всюду определённым, если добавить (при необходимости) одно бесполезное состояние N.

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

Глава 2 («Базисные конечные автоматы -определения, примеры и алгоритмы построения»)

Во 2-й главе определяется новый объект в теории конечных автоматов Рабина-Скотта - так называемый базисный автомат для заданного регулярного языка Ь. Этот автомат является единственным для данного языка Ь, причём является его инвариантом. Исследование базисных автоматов и является предметом представляемой диссертации.

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

К = (<Э,Е,6,8,Р) (1)

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

Ь = (2)

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

= (3)

автомат в канонической форме, определяющий зеркальный к Ь язык Ья. Бинарное отношение # определяется следующим образом:

А#Х тогда и только тогда, когда (Зги; е£) (и € е

где # С 2 х К, а <2 и 7?. - множества состояний автоматов в канонической форме Ь и ЬЕ соответственно. Очевидно, что существуют несложные алгоритмы построения этого бинарного отношения, т.е. приведённое определение конструктивно.

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

Определение 1 Автомат

(Т,Е,6г,ЗТ,РТ)

над некоторым алфавитом I! для следующих множеств Т, 5?, Бт и Рг■'

• Т = {(Л, X) | для любого А € Я, X 6 11, АфХ} (обозначим А как а(Т), X как 0{Т) дляТеТ);

• для любых Ту, Т2 6 Т, а € £ мы имеем 5т{Т\, а) Э Т2 если и только если ^аЫТ:),а) Э а(Т2) и 6я(р(Т2),а) Э /?(Тг);

• Т 6 если и только если а(Т) = зд (это означает, что а(Т) единственное начальное состояние Ь, т.е. SQ);

• Т € ^г и только если 0(Т) = йд (это означает, что 0(Т) -единственное начальное состояние автомата Ьт.е. йк,)

назовём базисным автоматом для данного языка Ь и обозначим через ВА(Ь).

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

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

М-

Для заданного регулярного языка Ь рассмотрим определяющий его произвольный НКА К, а также произвольный всюду определённый автомат (по определению являющийся детерминированным)

Для этой пары автоматов К и 2 <Рк2 '■ <2 —> является полной функцией

разметки (в дальнейшем, для краткости, функцией разметки), если для каждых 9 € <5 и ¡7 € €¿2 множество содержит д в том и только том случае, если

. (4)

Последнее определение можно считать и алгоритмом построения функции <Рх2, поскольку £}"(<?) и - регулярные языки. Отметим, что в

процессе построения эквивалентного канонического автомата, выполненного

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

В разделе 2.4 рассмотрен подробный пример построения базисного автомата для языка, заданного регулярным выражением (а + аЬ + Ьа)*. Граф переходов автомата К, одного из НКА, задающих данный регулярный язык, показан на рис. 1. Изменив на этом рисунке направления стрелок на противоположные, получим граф переходов зеркального к К автомата КЕ, задающего инверсный язык

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

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

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

В рассматриваемом нами примере из равенства Ь = ЬЕ следует, что графы переходов автоматов Ь и Ьк совпадают. Состояния автомата Ья обозначены через X, У и И (вместо А, В и С).

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

= <р°к%2) = {х,г}, <р°ки%) = {¥}.

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

для входных языков, например, являются слова:

ааЬ 6 £}?Ы П С%(А), а € 4"Ы П С%{В), 4"Ы П £«(С) = 0 ;

а € П 4"(В), 4"Ы П 4"(А) - ££Ы П С%{С) = 0 ;

аЬ 6 ££Ы П 4"(Л), Ь 6 П 4"(С) 4г(?з) П £*(£>) = 0 ;

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

Для получения значений обратной функции разметки = г(ч))

можно считать, что:

ааЪ 6 Л С%{Х), а е 4"*Ы П Г* (У), (?1) п £§ (Л) = 0 ;

и так далее, в силу Ь = Ья.

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

X У z

A # 4

В # # #

С #

По определению автомата ВА(Ь),

г = {(Л, X), (А, У), (В, X), (в, У), (в, г), (с, у)},

и ВА(Ь) может быть определён следующей таблицей:

a b

- - (A,X) {B,Z) (C,Y)

(A,Y) (B,X),(B,Y)

<- (B,X) (.B,Z) (A,Y)

(B,Y) (B,X),(B,Y)

(B,Z) (A,X)

(C,Y) {A,X),{A,Y)

Таблица 2

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

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

Сам алгоритм построения отношения # описан, например, в следующей статье: Melnikov В. A new algorithm of the state-minimization for the nondeterministie finite automata // The Korean J. of Сотр. and App. Math. - V. 6. - No. 2. - 1999. - 277-290.

• в состояние (£?,.£), помеченная а, так как Ь имеет дугу из В в В, помеченную а, и Ь11 имеет дугу из 2 в X, помеченную также а;

• в состояние (Л,"К), помеченная 6, так как Ь имеет дугу из В в А, помеченную Ь, и Ьн имеет дугу из У в X, помеченную также Ь.

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

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

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

Утверждение 1 Автомат B4(L) эквивалентен автомату L.

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

21 Про однозначные и неоднозначные автоматы ем., например, в следующей статье: Мельников Б. Однозначные конечные автоматы // Известия ВУЗов. Серия «Технические науки» (Поволжский регион). - 2002. - К'2. Важно отметить, что сформулированные в ней критерии однозначности используют функции разметки состояний, и, следовательно, напрямую связаны с вопросами, рассматриваемыми в данной диссертации.

Рис. 4

однозначные автоматы, детерминированные автоматы, автоматы в канонической форме.

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

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

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

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

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

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

Рассмотрим единственную последовательность состояний автомата ß4(L), такую что B4(L) читает буквы слова и и проходит свои состояния в следующем порядке: (Л0,Х0), (Ai,X\), (А2,Х2), ■ ■■, {Ап,Хп).

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

Qa, Ii, 42,

Утверждение 4 <р1к(яд э и Рхи((и) э для любого г = 0,1,... ,п.

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

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

• Mehiikov В. On an expansion of nondeterminisiic finite automata // J, of Applied Mathematics and Computing, Springer Berlin/Heidelberg. - Vol. 24, No. 1-2. - 2007. - 155-165.

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

В разделе 2.8 рассматриваются ещё два примера построения базисного автомата. Эти примеры демонстрируют выполнение свойств, описанных в предыдущих разделах.

В разделе 2.9 приведён альтернативный алгоритм построения дуг базисного автомата. Кратко опишем его, применяя следующие обозначения. Дуги автоматов Ь и ЬЕ будем обозначать заглавными греческими буквами, не совпадающими по написанию с латинскими - до буквы 5 для автомата Ь и начиная с буквы П для автомата Ьп, а также для зеркального к последнему автомата (Ьк)к. Для некоторой конкретной дуги Г, идущей из вершины А в вершину В и имеющей пометку а С Е, будем писать а°(Г) = А и /?а(Г) = В.

Выберем некоторую букву а € 2; описанную здесь процедуру мы проделаем для каждой буквы алфавита. Пусть - помеченые буквой а дуги автомата

Ь (т.е. элементы множества <5 д), а ¿д - помеченые буквой о дуги автомата Ьк (т.е. элементы множества 8д). Аналогично сказанному выше, будем таким же образом обозначать соответствующее множество дуг автомата (Ьн)н.

Рассмотрим бинарное отношение #а С х ¿д, определённое следующим образом. Для некоторых Г е <5^ и П 6 5% полагаем Г#аП тогда и только тогда, когда для некоторого слова ш € Ь имеем представление ги = иаь, и при этом:

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

Утверждение 5 Пусть Г £ ¿д и Я £ - некоторые дуги канонических автоматов для языков Ь и соответственно. Тогда е базисном автомате ВА(Ь) имеется дуга

тогда и только тогда, когда

Глава 3 («Свойства базисных конечных автоматов»)

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

23Мы не применяем функции а° и /За к дугам автомата Ья (а применяем их к одноимённым дугам автомата {£,я)п).

и Є ££(аа(Г)), и є £^(аа({1)),

(6)

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

Утверждение 6

Утверждение 7

Утверждение 8

—

Утверждение 9

\

п

(

П ¿f®

\я£9к(я) J

С ЦК).

п

.£°Kut(q)CC(K).

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

Определение 2 Для некоторой пары состояний ПК А (1), т.е. для Ч\,Ч2 € (}, определим автомат 3М2{К), граф переходов которого получается из графа переходов автомата К следующим образом.

• Для каждого состояния г 6 <2, соответствующее множество дуг 7(171, г) заменяется на множество 7(дь г) и 7(172, г).

• Аналогично, для каждого состояния г € <5, множество дуг ^(г^г) заменяется на множество 7(г, 91) и 7(г, <?2) •25

24 Они были приведены без доказательств в статье Melnikov В. A new algorithm of the. state-minimization for the nondeterministic finite automata Ц The Korean J. of Сотр. and App. Math. - 1999. - V. 6. - No. 2. -277-290. В представляемой диссертации приводятся соответствующие доказательства.

25 Поэтому, если имеются какие-либо из следующих четырёх случаев: g'.g" £ {91,92}. тогда каждая дуга т(9'>9") Э а заменяется па. петлю 7(91,91) Э о.

• Состояние qi отбрасывается; соответствующие элементы функции переходов 7 также отбрасываются.

Кроме того, состояние qx автомата Jqiq,>(K) - стартовое (финальное) тогда и только тогда, когда по крайней мере одно из состояний qi, q2 является стартовым (финальным) в автомате К.

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

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

= (7)

Тогда для автомата К\ = Jm2(K) выполняется следующее равенство:

ЦК) = ЦК{). (8)

Кроме того,

(9)

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

<р0А<ь) = ч>%аЫ- (10)

Тогда для автомата К\ = Jgiq2(K) выполняется равенство

С(К)^С(Кг); кроме того, = <f(<7i) •

Далее, в разделе 3.3, приведены примеры применения алгоритма объединения состояний недетерминированного автомата.

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

Доказано, что канонический автомат LR содержит не более 2" -1 состояний (где п - число состояний автомата L)27. Этим же числом ограничивается число

26 Аналогично утверждениям 6 и 8, эти утверждения были приведены без доказательств в статье [16|. Доказательства были впоследствии опубликованы в следующей статье: Mclnikov В. Once more on the eige-minimization of nondeterministic finito autómata and the connected Problems // Fundamenta Informati-cae - 2010. - V. 104. - No. 3. - 267-283. В представляемой диссертации соответствующие доказательства не рассматриваются - однако рассматриваются примеры применения, связанные с основным объектом диссертации - базисными конечными автоматами.

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

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

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

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

С?{А) = С%Щ((А,Х)).

Утверждение 13 Пусть задан регулярный язык Ь, канонический для Ьп автомат (Ья)н, и X - некоторое состояние /А28 Тогда для каждого состояния А автолшта Ь выполнено следующее:

С$)Я(Х) = (с%(Х))Н = С^Щ((А,Х)).

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

Утверждение 14 Пусть задан регулярный язык Ь и его канонический автомат Ь. Тогда для некоторого состояния А автомата Ь выполнено следующее:

£~а1(А) = У С%ц((А,Х)).

хе<2

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

Ья выполнено следующее:

(с£{Х))Л = с^ (X) = и С%[Ь]((А,Х)).

АеП

Утверждение 16 Пусть канонический автомат Ь для данного регулярного языка Ь имеет по крайней мере два различных состояния20, и А, В - некоторая пара таких^состояний. Тогда существует состояние X канонического автомата Ьк, такое что базисный автомат для языка Ь содержит в точности одно состояние из следующих двух: (А,Х) и (В,Х).

28 Поэтому X может также рассматриваться как состояние автомата (Ья)л •

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

Утверждение 17 Пусть канонический автомат Lопределяющий язык LR, имеет по крайней мере 2 различных состояния, и X,Y ~ некоторая пара таких состояний. Тогда существует состояние А канонического автомата L, такое что базисный автомат для L содержит ровно 1 состояние из следующих: (А, X) и (Л, Y).

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

Глава 4 («Применение базисных автоматов в задачах минимизации недетерминированных конечных автоматов»)

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

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

Определение 3 Пара непустых подмножеств Q С Q и R С Ц образует псевдоблок, если выполняется следующее условие: (\Л4 &Q ,Х £ R) (А#Х).

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

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

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

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

,i0 См. также следующие статьи:

• Melnikov В. A new algorithm of the state-minimization for the nondetermmistic finite automata. - The

Korean Journal of Computational and Applied Mathematics. - Vol. 6, No. 2. - 1999. - 277-290.

Определение 4 Пусть Bj и Б? - некоторые псеедоблоки. Будем говорить, что ¿?2 покрывает В\, если

a(ßi)Ca(ß2) и ß{Bl)Cß{B2).

Определение 5 Назовём некоторое множество псевдоблоков полным, если для каждого элемента Т € Q х TZ существует некоторый псевдоблок В этого множества, такой что Т 6 В.ъх

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

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

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

Алгоритм 1

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

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

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

Метод.

• Melniiov в. Опте more about the state-minimization of the nondetorministic finite automata. - The Korean Journal of Computational and Applied Mathematics. - Vol. 7, No. 3. - 2000. - 655-662.

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

52 Подробнее см. следующую статью: Melnifeov В., Sciarim-Guryanova N. Possible edges сf a finite automaton defining the given regular language // The Korean J. of Comp, and App. Math. - V. 9. - No. 2. - 2002. - 475-485.

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

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

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

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

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

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

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

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

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

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

Алгоритм 2

Вход: заданный регулярный язык Ь.

Выход: конечный автомат, определяющий Ь и имеющий минимально

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

Метод.

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

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

• Построить множество дуг 6' следующим образом. Для некоторых двух вершин и С[2 (допускаем возможность дх = д2) и некоторой буквы

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

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

а € £ считаем 5'(д1,а) Э q2, если для некоторых А € «(91), X е В £ а^2) и У 6 /3(9г) е базисном автомате существует дуга

5Т((А,Х),а)в(В,У). 36

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

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

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

Глава 5 («Базисные автоматы и динамические функции риска

в эвристических минимизационных алгоритмах»)

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

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

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

— для вершинной минимизации НКА;

— для дуговой минимизации НКА;

— для звёздно-высотной минимизации НКА

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

• для эвристических оценок эффективности самих алгоритмов:

— апостериорных;

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

— выполняемых в процессе работы алгоритмов, например - в алгоритмах принятия решений для выбора разделяющего элемента в незавершённом методе ветвей и границ.

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

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

Глава 6 («Заключение»)

В заключении работы приводятся её основные результаты,

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

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

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

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

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

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

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

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

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

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

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

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

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

[1] Melnikov В., Meliiikova A. A new algorithm oj constructing the basis finite automaton // Informatika (Lithuania). - Vol. 13. - No. 3. - Lithuania. - 2002. - 299-310. (Рецензируемый журнал, рекомендованный ВАК.)

[2] Мельникова A.A. Базисные автоматы в решении проблемы оптимизации // Вестник Тамбовского университета. Сер. Естественные и техн. науки. -Т. 12. - Вып. 4. - Тамбов: Изд-во ТГУ. - 2007. - 492-494. (Рецензируемый журнал, рекомендованный ВАК.)

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

[4] Мельникова A.A. К вопросу о сходимости значений динамических функций риска Ц Вестник транспорта Поволжья. - Т. 24. - Вып.4. -Самара: Изд-во СамГУПС. - 2010. - 11-15. (Рецензируемый журнал, рекомендованный ВАК.)

[5] Мельников Б.Ф., Вахитова A.A. Звёздная высота конечного автомата // Учёные записки УлГУ. Фундаментальные проблемы математики и механики- - Вып.З. - Ульяновск: Изд-во УлГУ. - 1997. - 51-57.

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

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

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

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

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

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

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

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

[13] Melnikov В., Vakhitova A. Some more on the finite automata /'/ The Korean Journal of Computational and Applied Mathematics. - Vol. 5. - No. 3. - Korea.

- 1998. - 495-506.

[14] 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.

[15] Melnikov В., Melnikova A. Edge-minimization of поп-deterministic finite automata // The Korean Journal of Computational and Applied Mathematics. -Vol. 8. - No. 3. - Korea. - 2001. - 469-479.

[16] Melnikov В., Melnikova A. Some propertis of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics. - Vol. 9. - No. 1.

- Korea. - 2002. - 135-150.

Мельникова Александра Александровна

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

Специальность 01.01.09 - дискретная математика и математическая кибернетика

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

Подписано в печать 22.02.2012. Формат 60x90/16. Бумага писчая. Усл. печ. л. 1,6. Уч.-изд. л. 1,8. Тираж 100 экз. Заказ № 9.

Димшровградский ииженерно-технологическнй институт НИЯУМИФИ Редакционно-издательский отдел, 433510, Димитровград, ул. Куйбышева, 294