Введение к работе
Актуальность темы
Пик интереса к конечным автоматам Рабина-Скотта (или Медведева) пришёлся на середину прошлого века. Именно тогда и появились почти все самые важные и фундаментальные работы в этой области. Но вскоре интерес начал спадать и почти сошёл на нет примерно в начале 1970-х годов - с развитием теории детерминированных конечных автоматов. Учёные и исследователи было решили, что область изучена полностью и практически не содержит нерешённых задач, но потом обнаружилось, что конечные автоматы могут быть применены для решения проблем из смежных наук. В рамках решения таких проблем способ представления языка часто оказывается важнее самого языка. Например, чтобы язык занимал как можно меньше памяти при хранении в вычислительном устройстве, из множества автоматов, задающих данный язык, необходимо найти минимальный по числу состояний.
Некоторые такие проблемы могут быть решены при помощи универсального автомата, описанию и применению которого и посвящена настоящая диссертация. Развиваемая в ней теория применяется для решения различных задач теории регулярных языков, а также некоторых задач дискретной оптимизации, причём как в точных их постановках, так и в эвристических.
Конечные автоматы и такие тесно связанные с ними конструкции, как, например, (право)линейные грамматики и регулярные выражения (РВ), относятся к основным понятиям информатики. Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и алгоритмов. Эффективность применения именно конечных автоматов в различных задачах теории регулярных языков связана с тем, что, в отличие от некоторых других задающих регулярный язык формализмов, конечный автомат является вычислительной моделью.
Недетерминированные конечные автоматы впервые были рассмотрены в
середине прошлого века Ю. Медведевым , а также М. Рабином и Д. Скоттом . Позднее, прежде всего при применении НКА к решению различных прикладных задач, указанные автоматы модифицировались и обобщались многими авторами. Важным обобщением стали недетерминированные автоматы-распознаватели с магазинной памятью (push-down automata, МП-автоматы). Они были созданы как одно из средств автоматического перевода, но также используются для других целей программирования, в том числе в теории трансляции.
Рассматриваемый в данной диссертации формализм - недетерминированные конечные автоматы Рабина-Скотта (Медведева), как и МП-автоматы, является примером автоматов-распознавателей - в отличие от конечных автоматов- преобразователей (например, конечных автоматов Мили, Мура), которые в представленной диссертационной работе не рассматриваются.
Универсальный автомат за последние полвека описывался во многих работах, хотя до сих пор остаётся открытым вопрос, кто именно является его автором. Авторы одной известной статьи приписывают авторство К. Каррезу, ссылаясь на его отчёт, который, однако, так и не был опубликован. Приблизительно в то же время Т. Камеда и П. Вейнер в своей работе описали объект, который, как впоследствии выяснилось, есть не что иное, как универсальный автомат. Немного позже, и не в контексте проблем, которые обсуждались в упомянутых работах, Дж. Конвей предложил определение автомата, который тоже оказался универсальным.
Универсальный автомат, как следует из его названия, универсален: аналогично каноническому и базисному автоматам, а также бинарному отношению #, универсальный автомат является инвариантом заданного регулярного языка - при этом, в отличие от бинарного отношения #, является полным инвариантом; кроме того, он обладает другими важными свойствами, что позволяют использовать его в различных задачах и не только теории формальных языков. Так, универсальный автомат, допускающий заданный регулярный язык, содержит гомоморфные образы всех автоматов, задающих тот же язык. Другим следствием конструкции универсального автомата является вычисление минимального автомата для данного недетерминированного конечного автомата или приближений такого минимального автомата. Также универсальный автомат даёт элегантное решение проблемы звёздной высоты для некоторых классов язы- ков.
При этом алгоритмы построения универсального автомата, в том числе эвристические, ранее почти не исследовались, т.к. в большинстве работ он был, скорее, вспомогательным инструментом для поиска минимального автомата. Само определение универсального автомата в большинстве случаев можно рассматривать как алгоритм построения - однако он не является эффективным. А автомат СОМ первоначально был получен научным руководителем диссертанта с помощью более простых алгоритмов, чем совпадающий с ним универсальный автомат (это совпадение было доказано уже впоследствии, диссертантом). Это совпадение даёт основания полагать, что алгоритмы работы, получаемые на основе определения автомата СОМ, будут более простыми, чем алгоритмы, получаемые на основе определения универсального автомата - однако исследование подобных вопросов в данной диссертации только начато.
Целью работы является создание алгоритмов решения различных прикладных задач теории формальных языков с использованием универсального автомата Конвея.
Основные задачи исследования:
-
описание вариантов определения универсального автомата;
-
доказательство совпадения автомата СОМ с универсальным автоматом;
-
исследование свойств автомата СОМ, следующих из его определения;
-
создание практических алгоритмов решения прикладных задач теории формальных языков с использованием универсального автомата;
-
описание применения расширенных вариантов автомата СОМ для определения различных вариантов описания подклассов класса контекстно-свободных языков;
-
описание применения автомата СОМ для решения некоторых задач, связанных с созданием эффективных математических моделей в экономике;
-
применение современных инструментальных средств разработки программного обеспечения, в том числе средств объектно-ориентированного программирования.
Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева), в частности - универсальный автомат Конвея.
Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами, в частности - алгоритмы их эквивалентного преобразования.
Методы исследования
В работе использованы:
-
методы доказательства теорем дискретной математики;
-
математические методы разработки алгоритмов;
-
математическое моделирование;
-
современные методы создания программного обеспечения, объектно- ориентированное программирование.
Результаты исследования
Результатами диссертационного исследования являются новые утверждения и теоремы теории формальных языков, а также новые вычислительные алгоритмы работы с недетерминированными конечными автоматами.
Научная новизна
Доказано совпадение автомата СОМ и универсального автомата Конвея. Алгоритм построения автомата СОМ получен с помощью более простых для реализации алгоритмов, чем описанные ранее «алгебраические» алгоритмы построения совпадающего с ним универсального автомата. Вследствие этого алгоритмы работы с недетерминированными конечными автоматами (в частности, алгоритмы их эквивалентного преобразования), получаемые на основе определения автомата СОМ, более просты для реализации, чем алгоритмы, получаемые на основе определения универсального автомата.
Практическая значимость исследования
Полученные результаты могут быть применены при доказательстве теорем, связанных с регулярными языками и недетерминированными конечными автоматами, а также при описании алгоритмов эквивалентного преобразования конечных автоматов, в том числе при построении автоматов, эквивалентных заданному. Кроме того, результаты диссертации могут быть применены в различных за- дачах минимизации недетерминированных конечных автоматов - в вершинной, дуговой и звёздно-высотной минимизации, а также минимизации по некоторым комбинированным критериям. Помимо этого алгоритмы с построением универсального автомата находят своё применение в исследовании свойств специального расширения НКА, задающего КС-языки, а также в одном из подходов к моделированию микроэкономических процессов.
Достоверность результатов
Достоверность и обоснованность научных положений подтверждается приведёнными в диссертации доказательствами утверждений и теорем, соответствием результатов теоретических исследований экспериментальным тестам и расчётам, полученным на основе математического моделирования.
Основные положения, выносимые на защиту
-
-
Определение автомата СОМ и описание модели работы произвольного конечного автомата на основе автомата СОМ.
-
Исследование свойств автомата СОМ, следующие из его определения, и доказательство совпадения автомата СОМ с универсальным автоматом.
-
Алгоритмы решения прикладных задач теории формальных языков с использованием универсального автомата.
-
Модели, расширяющие класс конечных автоматов, и применение в них автомата СОМ для описания специальных подклассов класса КС-языков.
-
Вычислительные методы и алгоритмы минимизации автоматов с помощью автомата COM. Их применение для упрощения специальных математических моделей, сводящихся к НКА.
-
Программный комплекс, включающий построение автомата COM и реализацию рассматриваемых в диссертации прикладных задач, применяющих этот автомат.
Апробация результатов исследования
Основные научные и практические результаты исследований по теме диссертации докладывались на:
-
конференциях «Студенческие дни науки» Тольяттинского государственного университета (2010 г. и 2011 г.);
-
Всероссийском конкурсе научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий в рамках Всероссийского фестиваля науки (Белгород, 2011 г.);
-
конкурсе на лучшую научную работу студентов по естественным наукам Тольяттинского государственного университета (2011 г.);
-
научных семинарах кафедры прикладной математика и информатики Толь- яттинского государственного университета (2009-2013);
-
научном семинаре факультета математики и информационных технологий Ульяновского государственного университета (2012);
-
I Международной научно-практической конференции «Научная дискуссия: вопросы математики, физики, химии, биологии» (Москва, 2013 г.);
-
I Международной заочной научно-технической конференции «Алгоритмические и программные средства в информационных технологиях, радиоэлектронике и телекоммуникациях» (Тольятти, 2013 г.).
Публикации
Основные результаты диссертации опубликованы в 11 работах, 5 из которых опубликованы в изданиях, рекомендованных ВАК, и приравненных к ним.
Личный вклад автора
Постановка задач осуществлялась научным руководителем. Описываемые в диссертации математические модели вычислений, разработанные алгоритмы их решения и компьютерные реализации выполнены автором самостоятельно либо в соавторстве.
Структура и объём диссертации
Общий объём диссертации - 150 страниц. Диссертация состоит из введения, 9 основных разделов, заключения, списка используемой литературы из 83 наименований, а также предметного указателя и приложений.
Регулярные множества образуют класс языков, занимающий центральное положение по отношению к значительной части теории языков. Множество в заданном алфавите (конечном наборе атомарных символов) регулярно тогда и только тогда, когда оно либо пусто, либо содержит только «пустое» слово или однобук- венное слово, либо его можно получить из этих множеств путём применения конечного числа операций объединения, конкатенации и итерации.
К наиболее известным формализмам, описывающим регулярные языки, относятся регулярные выражения, детерминированные и недетерминированные конечные автоматы, регулярные (праволинейные) грамматики. В разделе также описывается ещё один метод задания регулярных языков, связанный с материалом настоящей диссертации, - п-подклассы.
п-подклассы нужно рассматривать в контексте т.н. последовательностных (sequential) языков. Контекстно-свободная грамматика с множеством правил Р называется последовательностной, если на множестве её нетерминалов можно определить такой линейный порядок, что ни одно из правил не содержит в правой части ни один из «предыдущих» нетерминалов. Контекстно-свободный язык называется последовательностным, если он порождается хотя бы одной последовательностной грамматикой.
Для определения л -подклассов наряду с целыми неотрицательными числами (множество N) рассмотрим эти же числа со штрихом, обозначая N' = (0', 1', 2', 3',... } и используя для элементов N'uN следующее естественное соглашение
Правило A ^a последовательностной грамматики называется правилом порядка к (к є N), если правая часть этого правила содержит А к раз, причём в
записи a = P0 AwP1 A(2)...pk _1 A(k)pk либо P0 =в, либо рк =в.
Правило A ^a последовательностной грамматики называется правилом порядка к' (к' є N'), если правая часть этого правила содержит А к раз, причём в
записи a = P0 A(1)p1 A(T)..pk _1 A(li )p к должно быть P0 Ф в , либо рк Ф в.
Порядком последовательностной грамматики называется наибольший порядок её правил. Порядком последовательностного языка называется наименьший из порядков порождающих этот язык грамматик. Для і є N u N' множество последовательностных языков, имеющих порядок, не превышающий i, будем обозначать л(і). Объединение всех л(і) будем обозначать При этом:
-
л(0) состоит из языков 0 и { в };
-
л(0') есть множество конечных языков;
-
представляет собой множество последовательностных языков;
-
и, наконец, л(1) есть множество регулярных языков.
Недетерминированные конечные автоматы (НКА) представляют собой пятёрку K={Q, Ъ, 5, S, F}, где:
-
Q - некоторое конечное множество состояний (вершин);
-
Ъ - рассматриваемый алфавит;
-
5 - функция переходов вида 5 : Q хЪ — P(Q), где P(Q) - множество всех подмножеств Q;
-
S cz Q - множество стартовых состояний (входов);
-
F zQ - множество финальных состояний (выходов).
Графически автомат можно представить как ориентированный граф, дуги которого помечены символами алфавита, а некоторые вершины помечены как стартовые или финальные. Поэтому в дальнейшем будут иногда использоваться термины вершина для обозначения состояния и дуга для обозначения перехода.
В качестве примера рассмотрим автомат для языка, определяемого регулярным выражением (a + ab + ba) . Графически он будет выглядеть следующим образом.
_ *
Рисунок 1 - Пример конечного автомата для языка, задаваемого РВ (a + ab + ba) .
Как и в случае с регулярными выражениями один и тот же регулярный язык может задавать бесконечное число НКА. Встаёт вопрос о поиске автоматов- инвариантов для заданного языка. Такими автоматами являются канонический (минимальный детерминированный автомат), базисный и универсальный. Кроме того, можно установить сюръективное отношение между множеством регулярных языков и множеством всех таблиц бинарного отношения #.
РАЗДЕЛ 1. Применяемый подход к исследованию регулярных языков
Для некоторого регулярного языка L и некоторого конечного автомата K={Q, Ъ, 5, S, F}, задающего этот язык, а также для канонического автомата L ={Q Ъ, 5q Sq, Fq} этого языка определим прямую функцию разметки
Ф: Q -P(Q)
следующим образом. Для любого qe Q и q^e Q ф (q) содержит qq в том и только том случае, если
LK (q) П LL (qQ) .
При этом положим ф 'n(q)= Ф l^r (q).
Данное определение несколько отличается от первоначального . В рамках его нет необходимости строить детерминированный автомат, эквивалентный заданному.
Далее рассмотрим специальное бинарное отношение # на множестве Qx R Q - множество состояний канонического автомата, а R - и множество состояний канонического к зеркальному. Для каждой пары A є Qи X є R положим A # X в том и только том случае, когда
(Suv є bju є L~ (A),vR є (X)).
Проще всего указанное отношение может быть получено при построении функции фш, рассматриваемой для автомата, зеркального к каноническому для за-
данного языка .
Отметим, что пары состояний отношения # могут рассматриваться как состояния базисного автомата для данного языка. Кроме того, отношение # также формирует множество т.н. псевдоблоков.
В качестве примера рассмотрим данное отношение для языка, задаваемого регулярным выражением (a + ab + ba) (автомат приведён на рисунке 1). Эквивалентный ему канонический автомат изображён на рисунке 2, а. Язык в данном случае совпадает с инверсным, поэтому канонический автомат к инверсному языку совпадает с каноническим автоматом заданного языка.
-
b)
Рисунок 2 - а) Канонический автомат для языка, задаваемого РВ (a + ab + ba) ;
канонический автомат языка, инверсного к нему.
Таблица 1 - Таблица отношения # для языка, задаваемого РВ (a + ab + ba) .
На основе этих автоматов, согласно определению бинарного отношения #, получаем таблицу 1.
Будем говорить, что пара подмножеств Q с Qи R с R образует псевдоблок, если для любых A є Qи X є Rвыполняется A # X. Если, кроме того, любая пара множеств Q' и R', таких что Q с Q'с Qи R с R'с R образует псевдоблок тогда и только тогда, когда Q' = Q и R' = R, то будем говорить, что пара Q и R образует блок.
Обозначим псевдоблок записью B(Q, R). Для такого псевдоблока В через а(В) обозначим соответствующие ему состояния Q с Q а через P(B) - соответствующие состояния R с R
Для приведённого выше примера выпишем псевдоблоки:
{A, B} х {X}; {B} х {X, Y, Z}; {A, С} х { Y}; {B} х {Y, Z};
{B, С} х {Y}; {A, B} х {Y}; {A} х {X}; {С} х {Y};
{A, B} х {X, Y}; {A} х {Y}; {B} х {X, Z}; {B} х {X, Y};
{A, B, С} х {Y}; {A} х {X, Y}; {B} х {Y}; {B} х {X}
{B} х {Z}. Выберем из них блоки
b = {A, B} х {X, Y}; b2 = {B} х {X, Y, Z}; Ьъ = {A, B, С} х {Y}. (1) Состоянию любого конкретного автомата для данного языка соответствует некоторый псевдоблок. Более того, очевидным необходимым условием для определения данного языка конечным автоматом является то, что подмножество псевдоблоков, соответствующих множеству состояний рассматриваемого автомата, покрывает все элементы отношения #.
РАЗДЕЛ 2. Автомат COM
Во 2-м разделе сначала описывается множество возможных дуг произвольного недетерминированного автомата, определяющего заданный регулярный язык, после чего приводится определение автомата COM - основного объекта, рассматриваемого в данной диссертации.
Положим B2ES^B1, a) при одновременном выполнении следующих двух условий:
-
для любого дєа(Ві) выполняется Sq(q, a) с а(В2),
-
для любого qEP(B2) выполняется Sr(q, a) с P(B1), (2) где Sq и Sr - функции переходов канонических автоматов, задающих языки L и LR соответственно. Отметим, что в приведённом определении мы специально не допускаем возможности a = є.
Итак, для некоторых пар значений двух функций разметки автомата мы определили функцию, способ задания которой полностью аналогичен способу задания функции переходов недетерминированного конечного автомата Рабина- Скотта.
Для того чтобы состояние qeQ могло быть входным, необходимо выполнение условия SqE ф 'П (q), где Sq - (единственное) входное состояние канонического автомата.
Для того чтобы состояние qeQ могло быть выходным, необходимо выполнение условия sR e ф О" (q), где sR - (единственное) входное состояние канонического автомата для языка L .
Используя последние утверждения, опишем множества стартовых и финальных состояний автомата COM. Положим B1 e Sb, если одновременно выполняются следующие условия:
-
существует такое q1 єа (S1), что q1 є SqT,
-
существует такое q^ P (B1), что q^ Fr , (2') где Sq и Fr - множество стартовых состояний канонического автомата к данному и множество финальных состояний канонического к инверсному соответственно.
Положим B1 є Fb, если выполняются оба условия:
-
существует такое q1 єа (B1), что q 1 є Fqs
-
существует такое q^ P (B1), что q^ Sr , (2'') где Fq и S^ - множество финальных состояний канонического автомата к данному и множество стартовых состояний канонического к инверсному соответственно. Объединив все вышеперечисленное, определим автомат COM. Автоматом COM к заданному языку L называется пятёрка
COM (L) = {B, Z, Sb , Sb, Fb }, где:
-
B - множество всех блоков для L;
-
Z - алфавит;
-
Sb - функция перехода, определённая выше;
-
Sb с B множество стартовых состояний;
-
Fb с B множество финальных состояний.
Отметим, что это определение даёт алгоритм построения автомата СОМ.
a) b)
Рисунок 3 - а) Автомат COM без входов и выходов; b) автомат COM языка (a + ab + ba) .
В качестве примера продолжим рассмотрение регулярного языка (a + ab + ba) или, что то же самое, автомата, приведённого на рисунке 1. Мы уже получили блоки бинарного отношения # для этого языка (1). Таким образом, мы получили множество состояний автомата COM. Воспользуемся определением функции переходов Sb, чтобы построить дуги автомата COM. Согласно приведённым ранее определениям, для того чтобы в автомате COM существовала дуга c пометкой a из блока, к примеру, b1 в блок b2 необходимо, чтобы хоть одно состояние из a(b1) (т.е. из состояний A, B) канонического автомата имело переход с пометкой a в какое-нибудь состояние из a(b2) (т.е. в состояние B), при этом также необходимо, чтобы в каноническом автомате к инверсному языку имелась дуга с пометкой a из одного из состояний P(b2) (т.е. X, Y, Z) в какое-нибудь состояние из P(b1) (т.е. X, Y). В нашем случае дуга b —a^ b будет существовать в автомате COM. Проведя такие действия необходимое количество раз, получим автомат без входов и выходов (рисунок 3, a).
Согласно определениям входов и выходов для автомата COM, блок b является стартовым/финальным, если a(b) содержит стартовое/финальное состояние канонического автомата, а P(b) - финальное/стартовое состояние канонического автомата к инверсному языку.
Автомат COM для языка (a + ab + ba) приведён на рисунке 3, b.
РАЗДЕЛ 3. Универсальный автомат Конвея
Универсальный автомат имеет несколько определений . Приведём одно из них.
Псевдофакторизацией заданного регулярного языка L называется такая пара языков (X, Y) над алфавитом S, что для языка XY = {uv | u є X, v є Y} выполнено условие XY с L .
Факторизацией регулярного языка L называется его максимальная псевдофакторизация (X, Y), т.е. если X с X', Y с Y' и XY' с L, то X = X' и Y = Y'. Обозначим множество всех факторизаций языка L как Fl. В факторизации (X, Y) язык X называется левым фактором, а Y - правым фактором. Так как s L = L s = L , L является одновременно и левым и правым фактором, которому соответствуют правый фактор Ys и левый фактор Xs. Будем называть (Xs , L) стартовой факторизацией, а (Ys , L) - финальной факторизацией.
Утверждается, что язык является регулярным тогда и только тогда, когда число его факторизаций конечно.
Универсальным автоматом Ul для заданного регулярного языка L называется пятёрка
Ul = {Fl , S, 5 l , Sl , Fl }, где:
-
5l : Fl x S ^ P(Fl ) и (X', Y') є 5L ((X, Y), a), если XaY' с L;
-
Sl = {(X,Y) | є єX};
-
Fl = {(X, Y) є Fl | єє Y} .
Отметим, что данное определение не является конструктивным, т.е. оно не даёт алгоритма построения универсального автомата. Для получения такого алгоритма нужны дополнительные построения.
Утверждение. Универсальный автомат Ul задаёт язык L.
РАЗДЕЛ 4. Совпадение автоматов COM и универсального
В этом разделе рассмотрено понятие подавтомата и определены вспомогательные объекты, необходимые для доказательства совпадения автоматов COM и универсального автомата. Также в разделе приведено доказательство справедливости утверждения об этом совпадении.
Согласно определению, приведённому Лаллеманом , автомат
K' = {Q', Е, 8', S', F'} называется подавтоматом автомата K, если выполняются условия:
-
Q' с Q , S с (S n Q'), F с (F о Q');
-
8 '(q, a) с 8(q, a) для любых q є Q' и a єЕ .
Очевидно, что подавтомат определяет язык-подмножество, который в некоторых случаях совпадает с исходным языком.
Утверждение. Всякий задающий язык L минимальный (недетерминированный) автомат является подавтоматом универсального автомата, определяющего
этот язык.
Для доказательства равенства универсального автомата и автомата COM были даны другие связанные определения.
Будем называть автомат K = {Q , Е, 8 , S , F } псевдоподавтоматом автомата K, если он для некоторой функции h: Q^ Q удовлетворяет следующим условиям:
* *
-
любому состоянию q автомата K соответствует некоторое состояние q=
*
h(q ) автомата K;
-
для каждой пары состояний qi и q2 автомата K условие q2 єо (q*, a) выполняется тогда и только тогда, когда для автомата K и его состояний h(q*) и h(q*) выполняется h(q*)є8^^*),a).
Для любых a єЕ, q*, q* є Q дуга q* —a^ q* соответствует дуге
h(q2) —h(q*), если выполняются условия q* єб*^*, a) и h(q* ) єб^^*)^). Очевидно выполнение следующих утверждений.
LK*(q*) сL-(h(q*)) и LK*(q*) сLf(h(q*)). Далее определим наполненный псевдоподавтомат. Таковым назовём псевдоподавтомат, в котором можно выделить подмножество дуг, соответствующее множеству дуг исходного автомата.
Помимо приведённых определений, было дано другое - основанное на определении функции разметки состояний. Автомат K' называется подавтоматом K, если для любого состояния q' автомата K' множество ^kk' (q ') непусто, причём обратное утверждение (для любого состояния из K) может быть неверно.
Пусть для заданного регулярного языка L построены универсальный автомат и автомат COM.
Теорема. Ul = COM(L) (с точностью до переобозначения состояний). Доказательство. Универсальный автомат задаёт язык L, и всякий автомат, определяющий этот язык (в том числе и COM(L)), является подавтоматом уни-
версального . Автомат COM(L), кроме того, является его наполненным псевдоподавтоматом, что следует из определений, приведённых выше.
Автомат COM - инвариант языка, см. [2]. Любой автомат для заданного
языка является подавтоматом и псевдоподавтоматом COM a . В частности, универсальный автомат является подавтоматом и наполненным псевдоподавтоматом, что следует из определения факторизации.
Итак, автомат COM является наполненным псевдоподавтоматом универсального, а универсальный автомат, в свою очередь, является наполненным псевдоподавтоматом автомата COM. Следовательно, согласно приведённому выше определению наполненного псевдоподавтомата, они совпадают.
РАЗДЕЛ 5. Применение универсального автомата - практические алгоритмы
Доказательство из предыдущего раздела не только (и не столько) доказывает приведённое выше равенство, сколько задаёт множество алгоритмов для различных задач (и в потенциале не только из теории формальных языков). Одной из наиболее важных возможных задач является задача минимизации, или, вернее, задачи минимизации - дуговая, вершинная и по звёздной высоте. Т.к. минимальный автомат (как и прочие) является подавтоматом автомата COM (или универсального, что одно и то же, как мы уже доказали), мы можем получить минимальный автомат (по нужной характеристике минимизации) последовательно исключая дуги (или простые циклы) из автомата COM.
Другим возможным подходом может стать построение минимального автомата на подмножестве множества блоков заданного языка, причём такое подмножество должно быть покрывающим. Т.е. задача минимизации в этом случае сводится к более общей задаче построения автомата на основе подмножества блоков. В диссертации предлагается 2 эквивалентных алгоритма построения такого автомата - приведём их краткое описание.
Алгоритм 1 (построение «снизу вверх»);
Вход: Подмножество множества блоков Q, канонические автоматы L и Lir . Выход: Конечный автомат (подавтомат универсального), соответствующий подмножеству Q.
Шаг 1: Строим блоки и соответствующие им вершины.
Шаг 2: Строим дуги по принципу построения дуг в автомате COM (согласно (2)). Шаг 3: Определяем входные и выходные состояния (согласно (2') и (2'')).
Алгоритм 2 (построение «сверху вниз»):
Вход: Подмножество множества блоков Q, универсальный автомат. Выход: Конечный автомат (подавтомат универсального), соответствующий подмножеству Q.
Метод: Удаляем в универсальном автомате все состояния (вместе с входящими в него и выходящими из него дугами), которых нет в заданном множестве блоков.
Несмотря на схожесть описания, практические реализации этих алгорит-
мов принципиально различны.Теорема: описанные алгоритмы эквивалентны, т.е. построенные на основе этих алгоритмов автоматы совпадают.
Справедливость этой теоремы следует из определения автомата COM.. Как уже было сказано выше, для построения минимального автомата рассматриваемое подмножество блоков должно быть покрывающим. Это условие
почти всегда обеспечивает эквивалентность минимального автомата и исходного, которая является фундаментальным условием минимизации.
РАЗДЕЛ 6. Возможная неэквивалентность исходного и покрывающего автоматов
В 6-м разделе рассматривается проблема неэквивалентности покрывающего автомата и исходного. В процессе построения минимального автомата мы определённым образом (индивидуально для каждого типа минимизации) выбираем
блоки из таблицы бинарного отношения #, чтобы получилось покрывающее
множество . Однако покрывающий автомат - автомат, построенный на покрывающем подмножестве блоков в соответствии с одним из алгоритмов из раздела 5 - в некоторых случаях может оказаться неэквивалентным исходному. Такая
проблема характерна, например, для т.н. автомата Waterloo и некоторых друзо
гих, не столь известных .
Таблица 2 - Таблица отношения # и блоки для неё.
(1) {A, B} х {X, Y}
(2) {B, C} х {Y, Z}
(3) {A, B, C} х {Y}
(4) {B} х {X, Y, Z}
Такая проблема требует от нас проводить дополнительные проверки в алгоритмах минимизации (прежде всего - в эвристических алгоритмах) - например, на соответствие циклов строимого автомата циклам базисного автомата. В алгоритмах минимизации автомата предугадать наличие в данном автомате некоторого конкретного блока - далеко не тривиальная задача: например, при построении практических алгоритмов возникает естественное предположение, что эта проблема присутствует для автоматов, приведённых в таблице 2, - поскольку минимальное покрывающее множество состоит всего из 2 блоков, которые, по первому предположению, не смогут обеспечить существование всех соответствующих циклов базисного автомата. Однако это предположение неверно - что проще всего удаётся показать путём реализации соответствующих алгоритмов.
Итак, при помощи специального программного обеспечения было сгене
рировано множество автоматов с различными характеристиками, для которых проводилась проверка на наличие проблемы, описанной выше. При практическом программировании не было обнаружено ни одного автомата, для которого покрывающий автомат был бы неэквивалентен исходному - однако в связи с естественными ограничениями на размерность задачи число состояний канонического автомата для рассматриваемого языка не превышало 25.РАЗДЕЛ 7. Подход к описанию контекстно-свободных языков с помощью расширения универсального автомата
В этом разделе предлагается новый возможный подход к проблеме описания языков, который заключается в следующем. Описывается специальный формализм, являющийся одним из возможных расширений класса недетерминированных конечных автоматов, который (формализм) описывает класс КС- языков. Далее определённым образом объекты этого формализма сводятся к «обычным» НКА, но определённым над новым алфавитом.
Для каждого n из множества N0, рассмотрим множества
N(n)={ 1, 2, ...,n-1, n} и Z(„)={-«, -(n-1), ..., -2, -1, 0, 1, 2, ..., n-1,n}. (Каждый элемент i из множества N(n) символизирует i-ю пару скобок. Также i символизирует i-ю открывающую скобку, а -i - соответствующую закрывающую скобку.)
Для заданного n > 0 будем называть [Z(n) ] языком, согласованным по скобкам (а каждое его слово - словом, согласованным по скобкам).
Рекурсивно определим слово, согласованное по скобкам:
в и 0 - согласованные по скобкам слова;
если w и V - согласованные слова, то u=vw - тоже согласованное по скобкам слово;
если w - согласованное слово, i є N(n), то u=iw-i - тоже согласованное по скобкам слово;
никакое другое слово не является согласованным по скобкам.
Таким образом, мы получаем новое согласованное слово из уже имеющегося путём заключения последнего в скобки и (или) приписывания к нему другого согласованного слова.
Определим скобочный автомат B следующим образом:
B=( Q, S, х, S, F, n ), (3)
где n из N0 определяет множество скобок Z(n), х - функция переходов вида
X: Q х Q ^ P ((Su{в })хZn)).
Далее определим язык автомата (3) - будем обозначать его записью L(B).
Пусть для последовательности q0, q1, ..., qm состояний из Q выполняются следующие условия:
q0 є S, qm є F;
(ak, ik) є X (qk, qk+1) для каждого к из множества {0, ..., m-1};
*
i1 i2 . im Є [Z(n) ].
Тогда мы считаем, что слово Q1 a2 . am принадлежит L(B). Никаких иных слов язык L(B) не содержит.
Скобочные автоматы B1 и B2 называются эквивалентными, если L(B1) =
L(B2).
Язык, задаваемый таким автоматом - это множество пометок всех маршрутов. В таких маршрутах можно выделить согласованные по открывающим и закрывающим скобкам пары циклов, одновременная вставка или удаление которых, снова даёт маршрут.
Теорема 1. Язык, распознаваемый автоматом (3), является контекстно-свободным.
Справедливо и обратное утверждение.
К автомату B, как и к классическим НКА, применяются различные алгоритмы эквивалентного преобразования (построение минимальных автоматов, универсального автомата и пр.).
Теорема 2. Пусть K1 и K2 - некоторые недетерминированные конечные автоматы над алфавитом , причем L(K1) = L(K2). Тогда L(B(K1))=L(B(K2)).
В результате преобразований получаются объекты, имеющие в некотором смысле более хорошие качества, причём не только как НКА над новым алфавитом, но и в исходном формализме, в том числе при обратном преобразовании.
Для этого введено понятие скобочных и правильных скобочных автоматов. Понятие правильных скобочных автоматов основано на том, что слова языка, определяемого этим автоматом согласованны по скобкам. При применении алгоритмов эквивалентных преобразований обычных НКА к скобочным автоматам последние сохраняют свою правильность.
РАЗДЕЛ 8. Применение универсальных автоматов
для моделирования некоторых процессов микроэкономики
Данный раздел описывает подход к оптимизации модели оптимального направления движения организации с использованием универсального автомата.
Рассматриваемая модель управления организацией зависит от критериев долгосрочной оптимальности, в число которых входят не только количественные, но и качественные показатели, связанные с нуждами организации и учи-
тывающие неопределённость исходной ситуации . Модель предполагает т.н. многофокусность управленческого действия, а также учитывает не только результаты, но и характеристики процесса достижения цели. Для последнего вводится понятие «ценностного ориентира» как основной характеристики организации, влияющей на скорость организационных и управленческих изменений в предприятии. Такая характеристика должна быть оптимальной по заданному набору критериев. Каждая организация формирует собственный набор ценностных ориентиров, которыми она будет руководствоваться при совершении т.н.
управленческих воздействий (УВ) . Процессы совершения УВ могут быть алгоритмизированы.
Был описан набор таких алгоритмов, реализованных с использованием аппарата сетей Петри. В описанном подходе моделирования УВ встаёт проблема минимизации числа состояний и (или) переходов в сети Петри, в решении которой может помочь аппарат теории недетерминированных конечных автоматов (НКА).
Для этого предлагается алгоритм оптимизации сетевой модели, который предполагает три этапа: сведение сети Петри к недетерминированному конечному автомату; оптимизация НКА; сведение оптимизированного НКА к новой сети Петри (модифицированной и имеющей, вообще говоря, меньшее число со-
бытий - но являющейся эквивалентной исходной). РАЗДЕЛ 9. Программный комплекс
В этом разделе приводится описание написанного в рамках работы над диссертацией программного комплекса. Он был реализован на языке Java с использованием парадигмы ООП. Некоторые модули были дополнительно написаны в
системе GAP. Программы не имеют пользовательского интерфейса и работают через консоль.
Они предназначаются для практического исследования закономерностей появления проблемы неэквивалентности покрывающего автомата и исходного. Помимо этого в комплексе был реализован алгоритм построения автомата COM.. Комплекс состоит из 5 модулей:
модуль чтения из XML;
модуль, реализующий логику работы автомата:
o построение зеркального автомата, o построение канонического автомата,
o построение универсального автомата и покрывающего автомата на основе покрывающего множества блоков;
модуль построения автомата из покрывающего множества блоков путём удаления состояний из универсального автомата;
модуль построения таблицы отношения #;
модуль нахождения блоков;
модуль нахождения всех возможных сочетаний блоков.
Программа принимает на вход XML документ, содержащий описание автомата (алфавит, количество вершин, переходы). Далее для заданного автомата последовательно строятся канонический, зеркальный и канонический к зеркальному. По каноническим автоматам идёт построение таблицы бинарного отношения #, затем в ней выделяются блоки, на основе которых создаётся универсальный автомат. После этого генерируются всевозможные наборы блоков, из которых впоследствии удаляются те, что не являются покрывающими для таблицы #. Для покрывающих наборов строятся соответствующие им автоматы. Они проверяются на равенство с заданным автоматом. Результатом работы программы является сообщение о наличии или отсутствии проблемы неравенства покрывающего автомата и заданного.
В качестве генератора автоматов в исследовании использовалось программное обеспечение, разработанное на основе алгоритмов случайной генера-
ции объектов в рамках комплекса работ, посвящённых исследованию репрезентативности сгенерированных дискретных структур.
При этом при помощи описанного программного комплекса были получены конкретные регулярные языки и соответствующие им конечные автоматы, обладающие специально сформулированными свойствами. Например, был получен покрывающий автомат, являющийся эквивалентным исходному, однако не имеющий состояний, простые циклы которых совпадали бы с простыми циклами некоторого состояния универсального автомата.
В заключении диссертации приведены её основные результаты и сформулированы возможные направления дальнейшей работы, связанные с рассматриваемыми в ней проблемами.
В приложениях приведены тексты программного комплекса с достаточными для понимания текстов комментариями.
Похожие диссертации на Применение универсального конечного автомата в прикладных задачах теории формальных языков
-
-
