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

УУ5552598

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

МЕЛЬНИКОВА Александра Александровна

БАЗИСНЫЕ КОНЕЧНЫЕ АВТОМАТЫ

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

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

Казань-2014

^ 8 СЕН 20Ц

005552598

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

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

Официальные оппоненты:

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

доктор технических наук, профессор Левин Виталий Ильич (профессор Пензенского государственного технологического университета)

кандидат физико-математических наук, доцент Богомолов Алексей Сергеевич (старший научный сотрудник Института проблем точной механики и управления РАН, г.Саратов)

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

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

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

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

им. Н. И. Лобачевского Казанского (Приволжского) федерального

университета.

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

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

диссертационного совета Д 212.081.24 при КФУ, кандидат физико-математических наук, доцент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Утверждения о свойствах таблицы состояний конечного автомата.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы Глава 1. Введение

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

конкретизируется предмет исследования — недетерминированный конечный автомат Рабина-Скотта (Медведева) для некоторого заданного регулярного языка L, говорится о различных способах задания автомата. В работе в первую очередь приметается задание НКА для некоторого регулярного языка L пятёркой вида К = (Q, Е, 6, S, F), где:

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

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

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

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

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

В работе используется также функция переходов вида -у : QxQ —>'Р(Еи {г:}), такая что для некоторой пары состояний <71,(72 £ Q 11 некоторой буквы о 6 Е условие 7(91,92) Э о считается выполненным при 6(qi,a) Э <72• Вводится определение зеркального к К конечного автомата KR = ( Q, Е, 5й, F, S), для кото[X)го 5Fi(ql, а) Э <72 выполнено тогда и только тогда, когда S(q2,a) В 9ь Автомат KR задаёт зеркальный (инверсный) к L язык

Через и обозначаются входной и выходной языки состо-

яния д, т.е. языки, определяемые автоматами

(Q,E,i,5,{?}) и (<?,£, <5, {<7},F)

соответственно. После получения детерминированного всюду определённого (total) автомата

¿r = (Q,£,Ms},F)

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

• {91,92} >~ {</з, <74}, если для некоторого а € имеем S(qi, а) = {<73} и ¿(92, а) = {Ы-

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

Рассмотрим - транзитивное замыкание отношения >-. При этом = С°£1{<11) тогда и только тогда, когда не выполнено условие {дьЫ >"+ Если выходные языки состояний 91 и д2 равны (т.е. эти состояния эквивалентны), то можно объединить эти состояния (при этом мы без ограничения общности считаем, что 92 - не вход):

• для всех вершин г € (5 множество дуг -у(г, (ц) заменяем на множество 7(г,<71) и7(г,д2)

• удаляем д2 и все дуги множеств -у(г, д2) и '/(<72,

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

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

Глава 2. Базисные конечные автоматы: определения, примеры, алгоритмы построения

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

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

Для произвольного НКА

К = {<2,Я,6,Я,Р) (1)

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

Автомат

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

Гп = (П,Х,6п,{зп},Рк) (3)

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

А#Х если и только если (3иу € Ь) (и е £'£(А),уп е ,

ГДе # ^ 2 х 72-, и Л. - множества состояний автоматов в канонической форме Ь и Ьп соответственно. Очевидно, что приведённое определение конструктивно - т.е. на его основе несложно описать алгоритмы построения этого бинарного отношения.

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

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

Определение 1 Автомат (7~, 6т, £У, Г?) над некоторым алфавитом Е для следующих множеств Т, 5т, Бх и /"У

• Т = {(Л, X) | для любого А € Я, X е. И, А#Х] (обозначим А как а(Т), X как /3(Т) для Те Т);

• для любых Т\, Тг € Т, а € Е мы имеем ¿т(Т\, а) Э если и только если 5я(а(Т1),а) В а(Т2) и 6п{р{Т2),а) Э /ЗСП);

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

• Те Рг если и только если (3(Т) = в-л (это означает, что /3(Т) -единственное начальное состояние автомата Ьп, т.е. вц)

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

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

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

Для заданного регулярного языка Ь рассмотрим определяющий его произвольный НКА К, а также произвольный всюду определённый автомат г = Для этой пары автоматов К к г Фкг <3 > является полной функцией разметки (в дальнейшем, для краткости, функцией разметки), если для каждых ц € <5 и д € С}г множество (?) содержит ц в том и только том случае, если

(4)

Последнее определение можно считать и алгоритмом построения функции поскольку ££'(<?) и ¿.'¿(я) - регулярные языки. В процессе построения эквивалентного канонического автомата можно получить другой алгоритм построения этой функции, что используется в примерах раздела 2.8 данной диссертации. __

Для канонического автомата К — (2, Е,<5, {3}, .Г), эквивалентного заданному К, функцию (т.е. когда рассматриваемые автоматы, ис-

ЛЛ

следуемый и канонический, эквивалентны) будем кратко обозначать и называть прямой функцией разметпки. Определим также функцию <Рк* •• <2 Р(тг): для каждого я € положим = <Ркя(я)- Эту

функцию будем называть обратной функцией разметпки.

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

Графы переходов автоматов Ь и Ьп приведены на рис. 2 и рис. 3:

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

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

¥>£Ы = {АЗ}, ч>Ш = {В), = {А,С};

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

X У 7

А # #

В # # #

С #

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

Т={(А,Х), (А, У), (В, X), (В, У), (В, Я), (С, У)}, и ВА(Ь) может быть определён следующей таблицей:

а Ь

—> <— (А,Х) (В, 2) (С,У)

(А,У) (В,Х),(В,У)

(В,Х) (В, 2) (А, У)

(В, У) (В,Х),(В,У)

(В, г) (А,Х)

(С, У) (А,Х),(А,У)

Таблица 2

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

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

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

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

1В работе не рассматривается бесполезное состояние N автоматов в канонической форме: несложно доказывается, что для бесполезных состояний канонических автоматов не может выполняться ни ни Л#Ы (для любых состояний А, X этих автоматов).

другим подобным случаям в теории формальных языков, однозначным (unambiguous); в противном случае - неоднозначным (ambiguous). Однозначные автоматы могут быть удобнее при использовании для решения различных проблем.

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

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

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

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

В разделе 2.7 доказывается свойство допускающего пути любого автомата для заданного регулярного языка, т.е. свойство автомата S4(L), связывающее его с произвольным автоматом К, допускающим рассматриваемый регулярный язык. Предположим, что слово и принадлежит языку L и число букв и равно п. Рассмотрим единственную последовательность состояний автомата BA(L), такую что BA(L) читает буквы слова и и проходит свои состояния в следующем порядке: (Ло, Х0), (Ах, Xi), (А2, Х2), • • •, (Ап, Хп). Рассмотрим также одну из последовательностей состояний, которые проходит автомат К при чтении слова и (для простоты будем рассматривать автоматы без е-переходов): 9о,9ь92, • • • ,9п- •

Утверждение 4 f^iqi) Э Ai и ^"'(9,) Э Х{ для i = 0,1,..., п.

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

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

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

Выберем некоторую букву а € описанную здесь процедуру мы проделаем для каждой буквы алфавита. Пусть - помеченные буквой а дуги автомата Ь (т.е. элементы множества 5о), а 5ак - помеченные буквой а дуги автомата Ьп (т.е. элементы множества 6я). Аналогично сказанному выше, будем таким же образом обозначать соответствующее множество дут автомата {Ьп)Е.

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

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

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

тогда и только тогда, когда Г#°Г2. Глава 3. Свойства базисных автоматов

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

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

V е £?'тг)), V € £°%.п(/Зат.

(5)

(6)

Утверждение 6 £ Ц^М '

Утверждение 7 С (и^м ®)" •

Утверждение 8 /#(«,) ■ ££"'(§)) С £(ЛГ).

Утверждение 9 £$(§))*" СкЬ)

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

Определение 2 Для некоторой пары состояний НКА (1), т.е. для 91,92 6 <5, определим автомат 3Ч1Я2(К), граф переходов которого получается из графа переходов автомата К следующим образом.

• Для каждого состояния г е <3, соответствующее множество дуг 7(?1,г) заменяется на множество 7(91,г) и 7(92, г).

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

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

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

Утверждения 10 и 11 определяют первый алгоритм объединения состояний. 3 На основе этих утверждений формулируются алгоритмы эквивалентного преобразования НКА, уменьшающие число его состояний.

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

_= <Р%Ы- (7)

2Поэтому, если имеются какие-либо из следующих четырёх случаев: <?',</' € {<?ь ф}, тогда каждая дуга 7(<7/><7/') Э а заменяется на петлю Э а.

3Эти утверждения в качестве предположений впервые были сформулированы автором диссертации в [19] (там же была приведена краткая схема доказательства) и впоследствии полностью доказаны в работе научного руководителя.

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

ЦК) = ЦК,). (8)

Кроме того,

<Р$(ч 1) = <(91)- О)

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

<Р°Ляг)=^Ля2)- (Ю)

Тогда для автомата К\ = 3'М1-(К) выполняется равенство

ЦК) = ЦК{)-, кроме того, = ^'Ы •

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

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

Доказано, что канонический автомат Ьв содержит не более 2" — 1 состояний (где п -.число состояний автомата Ь). Этим же числом ограничивается число возможных столбцов таблицы отношения #, в которой п строк. Кроме того, доказано, что в таблице соответствия состояний не может быть одинаковых строк и столбцов.

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

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

£?(А) = С"{Ц((АХ)).

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

С<$)Я{Х) = 0С^(Х))л = С$Щ{{А,Х)).

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

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

фА) = У С°£Щ{{А,Х)). хек

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

(С%(Х))Я = С?Гя (X) = и С&Щ((А,Х)).

Лей

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

(В,Х). _

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

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

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

4-я глава посвящена применению базисных автоматов в различных задачах минимизации недетерминированных конечных автоматов.

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

Определение 3 Пара непустых подмножеств <3 С 2 и й С К образует псевдоблок, если выполняется следующее условие: (УЛ 6 ^Д 6

Д) (А#Х).

Если, кроме того, любая пара множеств <2' и К, таких, что <2 С

Я: О. и Я С Я' С Т1, образует псевдоблок если и только если <5' = С} и В! = П, то будем говорить, что пара С} и Л образует блок.4

Для каждого псевдоблока В через а [В) обозначим соответствующие ему состояния (2 С <2, а. через в (В) - соответствующие состояния Я С. Л. При этом будем также обозначать данный псевдоблок записью В{(Э, Я).

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

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

а(В1)Са(В2) и Р(В1) С Р{В2).

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

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

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

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

4Как и ранее, не рассматриваем бесполезное состояние N.

Алгоритм 1

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

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

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

Метод.

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

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

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

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

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

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

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

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

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

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

Алгоритм 2

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

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

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

Метод.

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

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

• Построить множество дуг 6' следующим образом. Для некоторых двух вершин q\ и <72 (допускаем возможность 91 = дг^ и некоторой буквы а € £ считаем ¿'(<?1,а) Э <72, если для некоторых А 6 а(дО, X € В € а(9г) иУ € с базисном автомате существует дуга

6т((А,Х),а)э{В,У).

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

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

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

Глава 5. Заключение

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

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

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

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

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

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

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

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

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

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

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

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

[1] Melnikov В., Melnikova A. A new algorithm of 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. - 7G3-7G5. (Рецензируемый журнал, рекомендованный ВАК.)

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

[5] Мельников Б.Ф., Мельникова A.A. Многоаспектная минимизация недетерминированных конечных автоматов. Часть I. Вспомогательные факты и алгоритмы 11 Известия вузов. Поволжский регион. Физико-математические науки.

- № 4 (20). - 2011. - 59-69. (Рецензируемый журнал, рекомендованный ВАК.)

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

[7] Мельникова A.A. Некоторые свойства базисного автомата // Вестник Воронежского государственного университета. Серия «Физика. Математика». - № 2.

- 2012. - 184-189. (Рецензируемый журнал, рекомендованный ВАК.)

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

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

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

[11] Мельникова А.А. Свойства базисных конечных автоматов // Труды второй научн. конф. «Математическое моделирование физических, экономических, социальных систем и процессов». - Ульяновск: Изд-во УлГУ. - 1999. - С. 11.

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

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

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

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

(1С] 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.

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

[18] Melnikov В., Melnikova A. Edge-minimization of non-deterministic finite automata // The Koreau Journal of Computational and Applied Mathematics. - Vol. 8. - No. 3.

- Korea. - 2001. - 469-479.

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

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

- 110-114.

[21] Melnikov В., Melnikova A. Some more on the basis finite automaton /'/ Acta Universitatis Sapientiae. Informática. — Vol. 5. - No. 2. - Romania. — 2013. - 227-244.

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

Базиспые конечные автоматы

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

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

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

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