Как сделать из нка дка
конспекты занятий по курсу
4. Регулярные языки (продолжение)
4.1. Определённые и неопределённые КА
Суть различия в том, что в определённых автоматах ( deterministic automaton, ДКА) мы можем без возвратов определить допустимость заданной входной цепочки при её разборе, поскольку каждый переход при этом разборе однозначно определён.
Если же у нас неопределённый ( nondeterministic ) КА (НКА) , то выбрав в ходе разбора движение по той или иной развилке управления и не достигнув условия допуска цепочки, мы не можем быть вполне уверенными в том, что если бы мы не пошли по другому возможному пути, то не смогли бы допустить цепочку.
На деле это приводит к тому, что как в самих НКА, так и в тех программных распознавателях, которые строятся по НКА, вынуждены перебирать все возможные пути разбора для недопустимой цепочки, прежде чем уверенно вынести решение о её не принадлежности к заданному языку.
Более формально определение ДКА звучит так:
Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия:
(1) d ( q , e ) = Æ для любого q Î Q , и
(2) d (q, a) содержит не более одного элемента для любых q Î Q и a Î T .
Какой из видов представления КА лучше – вопрос не без лукавства (по крайней мере, пока не указано значимое окружение ( context ) задачи).
Вопрос в том, существуют ли обстоятельства, при которых НКА могут быть более предпочтительными, чем ДКА? Постарайтесь обосновать свой ответ.
Ответить на этот вопрос многим сразу будет затруднительно. Но он задаётся именно здесь, до изложения последующих алгоритмов, связанных с ДКА и НКА, именно потому, что подсказки к ответу, которые вы можете найти при изучении этих алгоритмов, куда быстрее будут замечены вами, чем если бы данная задача была поставлена в конце занятия (это один из итогов в т.ч. весьма основательных исследований т. н. когнитивной ( cognitive – познавательный) психологии, деятельно проводящихся с 60-х годов ХХ в.)
4.2. Алгоритм перехода РВ ® НКА
Пример 4.1. РВ ® НКА для языка < x Î < a , b >* : | x | a – чётно>
Из прошлого занятия мы знаем, что ему соответствует РВ
Перейдём от него пошагово, слева направо, по алгоритму к НКА.
Сначала будем приводить диаграмму состояний соответствующего НКА, а снизу – ту часть РВ, которой он соответствует.
Рис. 4.1. Полученный по алгоритму НКА, соответствующий РВ ( a )
Рис. 4.2. НКА для РВ ( b *)
Рис. 4.3. НКА для РВ ( ab * a )
Рис. 4.4. НКА для РВ ( ab * a | b )
Рис. 4.5. Полученный по алгоритму итоговый НКА, соответствующий РВ ( ab * a | b )*
4.3. Алгоритм перехода НКА ® ДКА
Этот алгоритм также подробно описан в [1] (с. 57-58).
Пример 4.2. НКА ® ДКА для языка < x Î < a , b >* : | x | a – чётно>
Замысел алгоритма прост и, разве что возникает вопрос с какого состояния исходного НКА начать. В данной задаче это удобно сделать с начального состояния.
1. Определим совокупность состояний НКА, в которые можно попасть по e из его начального состояния. Это состояния
Новое состояние ДКА, пока алгоритм не завершился, удобно назвать как их перечень
( K - I - A - G - L ), а только потом переименовать более кратко. Назовём этот перечень состояний текущим. Если полученное состояние ДКА нам ещё не было известно, запоминаем его.
2. Определяем совокупность состояний НКА, в которые можно попасть по каждому непустому знаку основного алфавита из текущего перечня состояний НКА.
По знаку (а) мы можем попасть:
из K , I и A – в B (а оттуда по e – в C и E ). Из G и L по (а) никуда попасть не можем.
То есть d ( K-I-A-G-L, a ) = B-C-E .
По знаку ( b ) мы можем попасть из K - I - A - G - L в состояние H и связанные с ним по e , т.е. в
То есть d ( K-I-A-G-L, b ) = H-J-I-A-G-L .
Оба полученных нами перечня состояний ранее нам не встречались. Запоминаем их, последовательно делаем их текущими и определяем, куда из них можно попасть по каждому из основных знаков алфавита КА (применяем к каждому из них п. 2).
Пока удаётся выявлять новые состояния ДКА, продолжаем:
Переходы из B - C - E :
d (B-C-E, a ) = F-J-L-I-A-G
d (B-C-E, b ) = D-E . Оба состояния нам ранее не встречались, запоминаем их.
Переходы из H - J - I - A - G - L :
d (H-J-I-A-G-L, a ) = B-C-E
d (H-J-I-A-G-L, b ) = . H-J-I-A-G-L
Переходы из F - J - L - I - A - G :
d (F-J-L-I-A-G, a ) = B-C-E
d (F-J-L-I-A-G, b ) = . H-J-I-A-G-L
Переходы из D-E :
d (D-E, a ) = F-J-L-I-A-G
d ( D - E , b ) = . D - E
Все полученные состояния соответствующего ДКА и переходы между ними нами исследованы, поэтому останавливаемся: алгоритм завершён.
Для удобства работы с новым ДКА переобозначим его состояния более кратко, например:
Рабочие обозначения состояний ДКА
Более краткие обозначения
d ( K-I-A-G- L , a ) = B-C-E
d ( K-I-A-G- L , b ) = H-J-I-A-G- L
d (B-C-E, a ) = F-J- L -I-A-G
d (B-C-E, b ) = D-E
d (H-J-I-A-G- L , a ) = B-C-E
d (H-J-I-A-G- L , b ) = . H-J-I-A-G- L
d (F-J- L -I-A-G, a ) = B-C-E
d (F-J- L -I-A-G, b ) = . H-J-I-A-G- L
d (D-E, a ) = F-J- L -I-A-G
d (D-E, b ) = . D-E
d ( A , a ) = B
d ( A , b ) = C
d (B, a ) = D
d (B, b ) = E
d (C, a ) = B
d (C, b ) = C
d (D, a ) = B
d (D, b ) = C
d (E, a ) = D
d (E, b ) = E
Заметим, что те состояния ДКА, в состав которых входят заключительные состояния НКА (в нашем НКА это состояние L ), также являются заключительными. То состояние ДКА, в которое входит начальное состояние НКА (у нас – К) – начальное. Поэтому, в новых обозначениях, заключительными для ДКА являются состояния A , C и D , а начальным – А.
Рис. 4.6. ДКА, полученный по алгоритму из НКА, соответствующий РВ ( ab * a | b )*
Любопытно, что полученный КА имеет 5 состояний, хотя мы знаем, что можно было бы обойтись и двумя. Для минимизации конечных автоматов разработан свой алгоритм, к которому мы вернёмся чуть позже, а пока рассмотрим прямой переход из РВ в ДКА.
4.3. Алгоритм перехода РВ ® ДКА
Известен алгоритм прямого перехода из РВ в ДКА, также приведённый в [1] . В силу лаконичности описания некоторых действий алгоритма, его понимание встречает сложности у части учащихся. Поэтому приведём подробный пример его применения для того же РВ ( ab * a | b )*.
Для нашего случая:
Необходимость такой нумерации связана с тем, что один и тот же знак (из Т) может несколько раз встречаться в одном и том же РВ и необходимостью точной ссылки на определённое вхождение данного знака в данном месте РВ. Так, b встречается в нашем РВ как на втором, так и на четвёртом месте, но если мы назовём порядковый номер, например, 4, то однозначно укажем какое именно вхождение данного знака в РВ имеется в виду.
2. Далее полезно построить дерево, соответствующее данному РВ. Заметим, что при определённом опыте использования алгоритма этот шаг можно и опустить, но наглядность дерева заметно облегчает освоение алгоритма и число возможных неточностей при его применении.
Напомним, что дерево строится по РВ слева направо, а каждый знак из Т в порядке следования его в РВ и каждое действие (объединение, конкатенация, итерация) отмечается на нём отдельной вершиной. Получившееся дерево представлено на рис. 4.7.
Здесь слева от каждой вершины и узла дерева проставлены номера мест знаков в РВ, с которых может начинаться соответствующая данному участку дерева подцепочка в РВ, а справа – номера мест ( position ), на которые она может окончиться.
Для отдельного знака (вершины дерева) соответствующие значения совпадают с номером знака в РВ. Для узлов – согласно свойствам соответствующих операций. В пособии вычисление этих значений приведено с привлечением функций firstpos () и lastpos (), а также nullable (), учитывающей вероятность возникновения пустой цепочки при использовании итерации в РВ.
Недетерминированные конечные автоматы
Просто конечные автоматы
Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:
- Q – конечное множество состояний.
- Σ – конечное множество входных символов.
- δ – функция перехода. Аргументы – состояние и входной символ, результат – состояние.
- q 0 – начальное состояние, принадлежит Q.
- F – множество допускающих состояний, является подмножеством Q.
И функционирующие следующим образом:
- Автомат начинает работу в состоянии q 0 .
- Если автомат находится в состоянии q i , а на вход поступает символ b, то автомат переходит в состояние δ(q i , b).
Возможно, более простым вам покажется следующее определение: детерминированным конечным автоматом называется такой автомат, в котором при любой данной последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. – прим.ред.
Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.
ПРИМЕЧАНИЕ
Это определение конечного автомата используется в теории вычислений. Автоматы Мура и Мили используются, в основном, при проектировании цифровой аппаратуры.
Конечные автоматы удобно изображать графически. На рисунке 1 приведён несложный ДКА, допускающий цепочки из 0 и 1, заканчивающиеся символом 0. Начальное состояние помечено входящей в него стрелочкой (да, этот здоровенный треугольник в душе – стрелочка), допускающее (в данном случае оно одно) – двойным кружком.
Рисунок 1. Простой детерминированный конечный автомат.
Второй вариант изображения автоматов – таблица переходов.
0 | 1 | ||
---|---|---|---|
-> | q 0 | q 1 | q 0 |
* | q 1 | q 1 | q 0 |
Добавляем недетерминированность
Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:
- δ – функция перехода. Аргументы – состояние и входной символ, результат – множество состояний (возможно – пустое) .
- Если автомат находится в состоянии q i , а на вход поступает символ b, то автомат переходит во множество состояний δ (q i , b) . Если автомат находится во множестве состояний , то он переходит во множество состояний, получаемое объединением множеств δ(q i , b).
НКА тоже распознаёт цепочки символов, цепочка считается допустимой, если после её обработки множество состояний, в котором оказался автомат, содержит хотя бы одно допускающее. Таким образом, НКА также задаёт некоторый язык.
На рисунке 2 изображён простой НКА, допускающий цепочки из 0 и 1, заканчивающиеся на 00.
Рисунок 2. Простой недетерминированный конечный автомат.
Этот же автомат в виде таблицы:
0 | 1 | ||
---|---|---|---|
-> | q 0 | ||
q 1 | Ø | ||
* | q 2 | Ø | Ø |
Разберёмся, как он работает.
Подход №1
Подход №2
Менее формальное, но немного более наглядное представление обработки той же цепочки тем же автоматом изображено на рисунке 3.
Рисунок 3. Обработка цепочки 100100
Рисунок 4. Немного изменённый НКА
Рисунок 5. Обработка цепочки 1001001.
Можно добавить слияние одинаковых веток, но это уменьшит наглядность. В подходе, основанном на множествах, слияние происходит автоматически – множество не может содержать два одинаковых элемента.
Подход №3
То есть, фактически, мы взяли дерево из подхода №2, и обрезали все ветки, кроме одной – наиболее успешной.
… и эпсилон-переходы
Небольшое полезное расширение стандартного НКА – ε-НКА, или НКА с эпсилон-переходами.
ПРИМЕЧАНИЕ
На рисунке 6 изображён пример ε-НКА.
Рисунок 6. НКА с ε-переходами.
Как это ни удивительно, но на этом немного странном примере продемонстрировано одно из наиболее полезных свойств ε-переходов – возможность простого объединения нескольких автоматов в один. В данном случае объединяемыми автоматами являются НКА, изображённые на рисунке 7, а результирующий автомат допускает цепочки, допустимые хотя бы одним из них.
Рисунок 7. Составные части автомата, показанного на рисунке 6.
Кроме того, обратите внимание, что никаких дополнительных ограничений на ε-переходы не накладывается. То есть:
- из одного состояния ε-НКА может выходить сколько угодно как обычных, так и ε-переходов;
- может существовать цепочка из нескольких последовательных ε-переходов;
- автомат может проходить цепочку целиком, частично или не проходить ее вообще (если у ε-НКА есть другие варианты поведения).
В общем, граф/таблица переходов автомата выглядят так, как будто во входном алфавите появился ещё один символ – ε, а его работа так, будто в любом месте обрабатываемой цепочки (в начале, в конце, между символами) находится произвольное количество этих символов. При этом для каждого состояния есть как минимум один переход по ε – в себя.
… и более формально
Введём понятие ε-замыкание .
- ε-замыканием состояния q i называется множество состояний ε-НКА, в которые из q i можно попасть по цепочке ε-переходов. Как минимум, в это множество входит само q i .
- Функцию, аргументом которой является состояние, а значением – соответствующее ε-замыкание, назовём eclose .
Функцию eclose можно определить так:
А теперь мы можем строго определить функционирование ε-НКА.
- Автомат начинает работать во множестве состояний eclose(q 0 ).
- Если автомат находится во множестве состояний , то он переходит во множество состояний, получаемое ε-замыканием всех состояний из объединения множеств δ(q i , a).
И почему это круто
Допустим, вам нужен автомат, распознающий двоичные, десятичные и шестнадцатеричные числа в стандартном ассемблерном формате (я понимаю, что такие ситуации происходят в вашей жизни нечасто, но я и так сломал голову в поисках не слишком искусственного примера). То есть, допустимая строчка должна описываться одним из следующих утверждений:
Решение показано на рисунке 8.
Рисунок 8. ε-НКА, распознающий числа в ассемблерном формате
Что в первую очередь радует в этом конечном автомате – то, что он понятен и изменяем . Посмотрев на граф, можно практически сразу сказать, что делает автомат, и убедиться, что он соответствует ТЗ. А если задание поменяется, граф будет достаточно просто изменить. Например, если добавляется ещё одна система счисления, нужно просто нарисовать соответствующий автоматик и присоединить его к начальному и допускающему состояниям исходного автомата ε-переходами.
Выполняющий аналогичную задачу ДКА приведён на рисунке 9 (что за цифры под состояниями – разберёмся позже, пока не обращайте внимания), он тоже не слишком сложен, более того, в данном случае даже получилось меньше состояний (а вот переходов больше, 78 против 60). Но сравните: насколько ДКА более запутан! Попробуйте, глядя на него, понять, что делает этот автомат, проверить, правильно ли он это делает, попробуйте добавить или убрать систему счисления, ещё как-нибудь изменить ТЗ…
Рисунок 9. ДКА, распознающий числа в ассемблерном формате.
ПРИМЕЧАНИЕ
В общем, мораль такая: с точки зрения проектирования конечных автоматов, ε-НКА – язык более высокого уровня, чем ДКА. Вычислительные возможности ε-НКА, просто НКА и ДКА совпадают – для любого ε-НКА теоретически можно построить ДКА, описывающий тот же язык (этим мы скоро займёмся), но проектировать ε-НКА гораздо, гораздо проще и удобнее.
На детерминированном компьютере проще всего реализовывать НКА, основываясь на его определении. То есть, хранить множество текущих состояний, а при обработке очередного входного символа, переходить из каждого состояния в соответствующее множество и объединять результаты.
Обработка входного символа:
Производительность
На первый взгляд, количество операций, необходимое для обработки одного символа можно оценить как O(M), где M – количество состояний автомата. Но эта оценка верна, только если вам удастся реализовать объединение множеств за константное время, не зависящее ни от размера первого множества, ни от размера второго.
Типичная сложность реализации объединения множеств линейно зависит от размера второго множества. Поскольку оценить мы его можем только как O(M), в результате сложность обработки одного символа – O(M 2 ), обработка строки длиной N – O(N*M 2 ).
Можно переписать код, например, так:
Но и в этом случае O(M 2 ) никуда не уходит, просто прячется внутри метода normalize.
Правда, это, конечно, оценка худшего случая – если все состояния соединены друг с другом всеми возможными переходами, в среднем всё будет не так печально.
ε-переходы
При желании таким же несложным способом можно реализовать и ε-НКА – нужно перед началом обработки данных и после обработки каждого символа подавать на вход автомату ε, пока множество состояний не перестанет изменяться. Примерно так:
Это ужасающе неэффективно, но зато работает.
Немного подумав, можно вспомнить про формальное определение ε-НКА через ε-замыкания, и сообразить, что множество eclose(q i ) – фиксировано, и его нужно вычислить только один раз, причём до начала работы автомата.
В результате, получаем вот такой код:
Этот кусок тоже имеет сложность O(M 2 ).
Реализация преобразованием в ДКА
Теория
Рассмотрим произвольный НКА с тремя состояниями – q 0 , q 1 , q 2 .
Независимо от своей внутренней структуры, в каждый конкретный момент этот НКА может находиться в одном из следующих множеств состояний:
И всё, других вариантов нет. Причём переход между множествами состояний чётко детерминирован – это просто объединение значений функции перехода для каждого из состояний, и сами значения и их объединения тоже находятся в этом списке.
Обобщая наблюдения до произвольного НКА с любым количеством состояний, мы можем определить следующий ДКА:
- его состояниями будут множества состояний НКА (цифры под состояниями ДКА на рисунке 9 обозначали соответствующие ему состояния НКА).
- начальным состоянием будет множество, состоящее только из начального состояние НКА.
- допускающими будут те состояния ДКА, которые содержат хотя бы одно допускающее состояние НКА.
Идея преобразования основана на том, что множество подмножеств конечного множества состояний – конечно, то есть, как бы НКА не крутился, он всегда находится в одном из конечного множества состояний.
ПРИМЕЧАНИЕ
Если мысль о том, что множества состояний одного автомата являются состояниями другого автомата, пока что плохо влезает в вашу голову, можно представить то же самое менее абстрактно. Для НКА с тремя состояниями, обозначим состояния ДКА следующими строчками:
Назначим среди этих состояний правильное начальное (оно должно соответствовать начальному состоянию НКА) и допускающие, нарисуем таблицу для функции переходов, получим ДКА.
Для НКА с большим количеством состояний – по аналогии.
С использованием индукции достаточно просто доказывается, что сконструированный ДКА описывает тот же язык (допускает точно те же цепочки символов), что и исходный НКА. Эта задача оставляется читателю в качестве упражнения :)
СОВЕТ
Индукционное предположение – в процессе обработки цепочки ДКА всегда находится в состоянии, соответствующем текущему множеству состояний НКА. База очевидна, для доказательства индукционного перехода нужно посмотреть на определение НКА и сравнить алгоритм вычисления следующего множества состояний с алгоритмом работы функции перехода нашего ДКА. А после всего этого сравнить, в каких случаях автоматы допускают цепочки.
Добавляем ε-переходы
- начальным состоянием ДКА будет ε-замыкание начального состояние ε-НКА.
Доказательство идентичности описываемых автоматами языков аналогично доказательству для обычного НКА.
ПРИМЕЧАНИЕ
Таким образом, можно считать доказанным, что любой язык, описываемый ε-НКА, может быть описан обычным ДКА. А поскольку обратное очевидно (ДКА это просто частный случай ε-НКА), вычислительная мощность ДКА и ε-НКА совпадают.
Просто хотелось отдельно отметить этот важный теоретический результат :)
Алгоритм
Состояния ДКА
Такое количество состояний немного пугает, но, к счастью, часто подавляющее большинство состояний оказывается недостижимым (то есть, не существует последовательности переходов, которая приводит автомат в такое состояние из начального), поэтому их можно просто отбросить, и это никак не повлияет на описываемый ДКА язык.
Рисунок 10. Неудачный НКА.
Генерация ДКА
Возможны два подхода:
- Сначала сгенерировать все состояния ДКА, которые только могут потребоваться, установить между ними связи, а потом избавляться от недостижимых состояний.
- Сразу же генерировать только достижимые состояния.
Мы пойдём вторым путём. Основная идея алгоритма:
- Начинаем с начального состояние ДКА – eclose(q 0 ). Оно достижимо по определению.
- Если состояние достижимо, то все состояния, в которые из него можно попасть, тоже достижимы.
- Из состояния q i можно попасть в те состояния, которые являются значением δ(q i , x), где δ – функция перехода ДКА, а x принадлежит множеству входных символов. Перебрав все входные символы, получим все такие состояния.
- После чего применяем к полученным состояниям тот же принцип. Остановка – когда все сгенерированные состояния рассмотрены подобным образом.
Производительность
Оценка алгоритма генерации ДКА неутешительна. Количество операций линейно зависит от количества состояний ДКА, а верхняя оценка для них – 2 M . В среднем будет получше, но тоже ничего хорошего – генерация новых состояний, то есть внутренняя часть цикла, это O(M 2 *S) операций (где S – количество символов).
Но зато, после того как ДКА сгенерирован, он обрабатывает любой символ за константное время, а строчку длиной N – за O(N).
Заключение
Ну а играть с автоматами проще всего в программе JFLAP, которая уже упоминалась выше.
Как уже известно, детерминированный конечный автомат (ДКА) характеризуется тем, что из каждого его состояния существуют единственные (!) переходы в другие состояния по каждой букве из алфавита \(\Sigma\). На прошлом семинаре мы ознакомились с графическим способом задания таких автоматов (рис. 1). Однако существует ещё и другой способ описания автомата c помощью матрицы переходов.
Матрица переходов для конечного автомата
В столбцах у нас все элементы алфавита \(\Sigma\), а в строках, соответственно, допустимые состояния из множества \(Q\). Таким образом, на пересечении \((i, j)\) элемента такой таблицы будет состояние \(q_k\colon q_i\xrightarrowq_k, \textq_i\in Q, w_j\in\Sigma\). Начальное состояние отмечено знаком \(\to\), а конечные (терминальные) – \(*\). Следующая таблица описывает автомат, изображённый на рис. 1:\[ \begin
Регулярные языки. Дополнение к языку
Регулярный язык — язык, для которого можно построить детерминированный конечный автомат. Таким образом, автомат на рис. 1 описывает регулярный язык \(L\), определяющий вхождение подстроки \(aa\) в рассматриваемом слове. Рассмотрим теперь язык \(\overline\), который назовём дополнением к регулярному языку \(L\).
То есть, в язык \(\overline\) входят все слова, которые не входят в регулярный язык \(L\). Если рассматривать язык автомата на рис. 1, то дополнением к нему будет язык, который определяет слова, в которых нет двух идущих подряд букв \(a\). Напрашивается вопрос: является ли само дополнение к регулярному языку регулярным языком?. Попробуем построить ДКА для такого языка. Для построения ДКА для \(\overline\) достаточно все конечные (терминальные) состояния объявить неконечными, а все остальные наоборот — конечными (т. е. инвертировать состояния): \[T_<\overline> = Q \setminus T_L\] Соответственно, если на автомате (рис. 1) состояния \(\\in T\), а \(\\notin T\), то тогда такой автомат описывает \(\overline\).
Таким образом, можно сделать вывод, что дополнение к регулярному языку — регулярный язык.
Разбор задачи для самостоятельного разбора из семинара 1
Попробуем построить такой автомат по индукции. Построим автоматы, определяющие слова, у которых \(1\) на последнем, предпоследнем и предпредпоследнем местах:
\(1\) – третья с конца
Соответственно, можно найти закономерности, благодаря которым возможно дальнейшее построение автоматов, для которых \(1\) на четвёртом, пятом, . десятом местах с конца. (Самостоятельно построить автомат для случая, когда \(1\) на десятом месте с конца).
На самом деле такое громоздкое рутинное задание было дано неслучайно. Рассмотрим теперь новый вид автоматов, который поможет решать нам такие задачки несколько проще.
Недетерминированные конечные автоматы (НКА)
В ДКА существует единственная последовательность действий, которая определяет, является ли слово частью языка (за счёт единственности переходов между состояниями). У нас уже были примеры автоматов, которые являются недетерминированными ( : по центру, справа). Рассмотрим автомат на рис. 2 и попробуем пройти по этому автомату словом \(01011\). По \(0\) у нас есть только один путь, поэтому проблем не возникает: \[q_0 \xrightarrow q_0\] По \(1\) мы уже не знаем куда перейти, соответственно, пройдём по всем возможным путям. Видим, что наше слово \(01011\) может как попасть в конечное (терминальное) состояние, так и не попасть. Попробуем описать формально все возможные переходы, рассматривая уже в случае нескольких возможных путей комбинации состояний: \[ q_0 \xrightarrow q_0 \\ q_0 \xrightarrow \ \\ \ \xrightarrow \ \\ \ \xrightarrow \ \\ \ \xrightarrow \,q_3\> \\ \] В НКА, если хоть один путь ведёт к конечному состоянию, то слово является частью языка. Таким образом, т. к. мы встретили после обработки слова конечное состояние \(q_2\), делаем вывод\(:\) \(01011\) является частью языка.
Теперь построить автомат, для которого \(1\) третья с конца будет проще:
Автомат с \(\varepsilon(\lambda)\)-переходами
Зачем они нужны? Если автомат находится в состоянии, из которого доступен \(\varepsilon(\lambda)\)-переход, он может его сделать за то же время, что он попадает в это состояние, т. е. в начальный момент времени в НКА, когда строчка ещё начинает вводиться, автомат сразу может совершить такой переход и оказаться в одном из двух состояний.
Рассмотрим автомат (рис. 3) и cлово \(baabb\). Начать с буквы \(b\) мы можем, совершив \(\varepsilon(\lambda)\)-переход. То есть наше слово определится автоматом следующей цепочкой\(:\) \(\varepsilon b\varepsilon aa\varepsilon bb\).
На самом деле, по НКА проще понять какую строчку он принимает, чем ту, которую он не принимает. Здесь работает такой подход: интуитивно для конкретной задачи определить возможные пути для конечного слова и построить его недетерминированным образом, а затем уже его можно детерминировать. Попробуем это сделать для следующего языка: \[L=\<\omega\in\<0,1\>^*\mid\omega\text< заканчивается на >010\text< или >101\>\] НКА для такого языка будет следующим:
Переход от НКА к ДКА
Из НКА можно получить ДКА следующим образом. Составим матрицу переходов для НКА, изображённого выше.
\[ \begin
На основе данной матрицы переходов строим следующий ДКА:
Такой метод построения ДКА называется методом построения подмножеств. Главные особенности:
- каждое состояние ДКА — множество состояний НКА (возможно и пустое множество);
- начальным состоянием ДКА будет множество, состоящее из начального состояния НКА и всех состояний, доступных \(\varepsilon(\lambda)\)-переходами;
- конечными состояниями ДКА будут те множества состояний НКА, которые содержат хотя бы одно конечное состояние НКА.
Следствие
Так как существует процедура, которая преобразует НКА в ДКА, то можем утверждать следующее:
Язык, для которого можно построить недетерминированный конечный автомат (НКА), также является регулярным языком
Задача 1
Преобразовать следующий НКА в ДКА.
Строим матрицу переходов для данного автомата: \[ \begin
Задача 2
Преобразовать следующий НКА в ДКА.
Операции над регулярными языками
Будем рассматривать два регулярных языка \(L_1, L_2\), для которых построены автоматы (рис. 4). Определим следующие операции над ними:
Объединение
Для построения НКА объединения автоматов \(L_1, L_2\) достаточно определить новое начальное состояние и организовать \(\varepsilon(\lambda)\)-переходы в начальные вершины этих автоматов (рис. 4).
Конкатенация
Для построения НКА конкатенации двух автоматов необходимо организовать \(\varepsilon(\lambda)\)-переходы из конечных состояний первого автомата в начальное состояние второго, а сами эти вершины перестать считать конечными (рис. 4).
Итерация (операция Клини)
Для построения НКА для итерации необходимо определить новое начальное состояние, которое будет ещё и конечным (для определения пустого слова как часть языка), и из всех конечных состояний организовать \(\varepsilon(\lambda)\)-переход в прежнее начальное состояние автомата (рис. 4).
Выход: ДКА .
Шаг 1. Пометить первый столбец таблицы переходов ДКА начальным состоянием (множеством начальных состояний) НКА.
Шаг 2. Заполняем очередной столбец таблицы переходов , помеченный символами, для этого определяем те состояния, которые могут быть достигнуты из каждого символа строкипри каждом входном символе. Поместить каждое найденное множество(в том числе) в соответствующие позиции столбцатаблицы, т.е.:
для некоторого >
Шаг 3. Для каждого нового множества (кроме), полученного в столбцетаблицы переходов, добавить новый столбец в таблицу, помеченный.
Шаг 4. Если в таблице переходов КА есть столбец с незаполненными позициями, то перейти к шагу 2.
Шаг 5. Во множество ДКАвключить каждое множество, помечающее столбец таблицы переходови содержащееНКА.
Шаг 6. Составить таблицу новых обозначений множеств состояний и определить ДКА в этих обозначениях.
Этот алгоритм обеспечивает отсутствие недостижимых состояний ДКА, но не гарантирует его минимальности.
Пример Пример 2.1. Дана регулярная грамматика с правилами. Построить по регулярной грамматике КА и преобразовать полученный автомат к детерминированному виду.
Построим по НКА из примера 2.1 ДКА.
1 Строим таблицу переходов для ДКА (таблица 2.2).
Таблица 2.2 – Построение функции переходов для ДКА
Автомат - это упорядоченная 5-ка вида , где:
.
Детерминированный автомат - то же самое, что просто автомат.
Недетерминированный автомат - автомат, в котором матрица переходов имеет сигнатуру >" width="" height="" />
, а >" width="" height="" />
- множество, \subseteq S>" width="" height="" />
.
Семантика [ ]
Автомат - это такая штука, которая кушает ленту с записанными на ней символами и согласно этим символам изменяет некоторую внутреннюю переменную. Когда лента заканчивается, проверяется значение переменной. Считается, что если переменная оказалась в состоянии, принадлежащем множеству допускающих, автомат принял строку, в противном случае наоборот. Теперь более формально. Имеется переменная state, вначале имеющая значение >" width="" height="" />
, и поток данных, в котором можно прочитать следующий символ при помощи некоторой функции, скажем, getchar (). Если поток данных неожиданно кончился, нужно проверить значение переменной state и напечатать результат. Иначе, заглянув в матрицу переходов, согласно ей изменить значение переменной state (" width="" height="" />
), после чего повторить всё сначала. Понятно, что в случае недетерминированного автомата переменная state - это множество (которое может быть представлено, скажем, списком), а изменение её значения - это map множества: .
-переходы [ ]
Автомат с " width="" height="" />
-переходами - недетерминированный автомат, в алфавите которого есть выделенный символ " width="" height="" />
, который никогда не встречается во входных данных, но, тем не менее, для него есть переходы в матрице " width="" height="" />
, при этом считается, что между любыми символами входного потока находится неограниченно много символов " width="" height="" />
. Более формально:
-переходов из множества состояний " width="" height="" />
:
-переходов на любую глубину:
Откуда следующий переход равен:
-переходы позволяют делать переходы там, где обычно их делать нельзя.
Реализация [ ]
Конечный детерминированный [ ]
Проще всего автомат представить массивом шириной в количество символов и высотой в количество состояний, при этом считая, что алфавит - это ASCII, множество состояний - это числа от 0 до высоты автомата, а начальное состояние - 0. Конечные состояния поставляются отдельно :)
После этого обработка такого автомата становится настолько очевидной, что я даже не буду приводить код.
Конечный недетерминированный [ ]
То же самое, что и детерминированный, только с заменой чисел на списки чисел, ну и в функции обработки придётся изменить нахождение следующего состояния на следующее множество состояний. Правда, тут возникает одна тонкость: простого List.map тут не хватит, надо ещё flatten'ом придавить, ну и одинаковые элементы убивать.
Конечный недетерминированный с
- переходами [ ]
А вот тут уже будет веселее. Во-первых, в наших автоматах сейчас просто нет места для " width="" height="" />
-переходов - всё занято обычными. Поэтому я предлагаю увеличить количество столбцов до 257 и для " width="" height="" />
использовать последний. Кроме того, нужно сначала обработать все " width="" height="" />
-переходы, а затем объединить их с обычными. Я предлагаю решить эту проблему следующим образом. Напишем отдельную функцию, которая будет производить переходы до тех пор, пока это не станет бессмысленно, то есть до тех пор, пока не будут найдены все доступные из данных состояний переходы. К сожалению, определение недетерминированных автоматов предлагает продолжать поиск до бесконечности, поэтому нужен критерий, показывающий, что больше ничего уже найдено быть не может. Моё предложение:
То есть всё новое, что было найдено, на самом деле не новое, а хорошо забытое старое.
Теперь написание кода становится достаточно очевидным.
Опять-таки, не стану приводить полный код применения автомата, ибо он очевиден.
Преобразование НКА в ДКА [ ]
, где n - количество состояний), их можно пронумеровать. Кроме того, можно определить, содержится ли в данном множестве хотя бы одно конечное состояние, и если да, то, значит, можно считать всё множество конечным состоянием. Наконец, каждому множеству состояний и каждому символу соответствует единственное следующее множество состояний. Таким образом приходим к очевидному выводу: занумеровав все множества состояний НКА, построив матрицу с длиной, равной количеству этих множеств и ширины 256 и записав в каждую ячейку номер соответствующего состояния, получаем обыкновенный ДКА.
), просто сгенерировав всю булеану, а можно оставить только состояния, которые этот автомат может принимать, устроив ему пробный пробег, то есть построив дерево всех возможных случаев.
Регулярные выражения [ ]
Сначала несколько слов, почему я не выделил для регексов отдельную статью. Во-первых, они эквивалентны автоматам. Во-вторых, эти две темы так тесно переплелись в билетах, что в этой отдельной статье пришлось бы также упоминать про автоматы, а хотелось бы иметь всю информацию в одной статье.
Синтаксис [ ]
Проще всего описать синтаксис регексов при помощи грамматики:
Преобразование в НКА [ ]
Сначала вспомним, что такое автомат.
Автоматом называется двумерный массив списков чисел (состояний), т.е. int list array array, причём:
Теперь будем рассматривать наиболее простые конструкции, после чего через них будем определять сложные, иными словами, применим восходящий стиль программирования.
- Итак, автомат, эквивалентный регулярному выражению "." имеет всего 2 строки: нулевая полностью забита единицами, вторая пуста.
- Выражению вида "A", где A - любой символ, соответствует автомат, пустой за исключением единицы в нулевой строке на месте символа A.
- "(A)" эквивалентно "A".
- А вот регулярное выражение "AB" уже так просто не сдастся. Ему соответствует такой автомат: верхняя часть эквивалентна A, нижняя - B, и между ними налажен " width="" height="" />
-переход из допускающего состояния A в начальное состояние B. - Выражению "A|B" похоже на "AB": ему соответствует автомат, в котором также верхняя и нижняя части эквивалентны A и B, причём из начального состояния A имеется " width="" height="" />
-переход в начальное состояние B, а из допускающего состояния A - в конечное состояние B. Таким образом получается что-то вроде параллельного выполнения. - "A?" эквивалентен автомат, имеющий " width="" height="" />
-переход из начального состояния в конечное. - "A+" порождает автомат, имеющий " width="" height="" />
-переход из конечного состояния в начальное. - И наконец, "A*" - это автомат, в котором имеется " width="" height="" />
-переход как из начального состояния в конечное, так и наоборот.
Построение по НКА [ ]
Утверждение номер раз. С НКА возиться долго и муторно, поэтому, как объяснено выше, преобразуем НКА в ДКА и расслабимся.
Утверждение номер два. Существуют два различных способа преобразования ДКА в регулярное выражение: первый - сложный и математический, второй - простой и человеческий. Начнём с первого.
Рассмотрим следующую штуку: >_^>" width="" height="" />
- множество подстрок, разбор которых начинается в состоянии " width="" height="" />
и заканчивается в состоянии " width="" height="" />
, причём номера состояний в промежутке между начальным и конечным не превышают " width="" height="" />
. Заметим, что \in D> <\mathbb
- все возможные слова. Нетрудно понять, что если уметь преобразовывать каждый из элементов объединения в регекс, то регулярным выражением, эквивалентным автомату, будет что-то вроде >_>^| <\mathrm
, где _^>>" width="" height="" />
- это регулярное выражение, соответствующее >_^>" width="" height="" />
. Таким образом, надо научиться строить регулярные выражения для таких элементов. Будем доказывать, что это возможно, по индукции.
(индукция по " width="" height="" />
)
Для начала введём некоторые вспомогательные функции.
- и регекс, соответствующий этим символам
):
Короче говоря, здесь надо просто сесть и подумать.
Второй алгоритм можно назвать "vertex elimination". Суть его состоит в том, что автомат представляется в виде графа, у которого последовательно уничтожаются все вершины, кроме начального и конечного состояний, а ссылки на уничтоженные вершины перенаправляются, делаются "сквозными". К сожалению, пример привести довольно сложно в связи с ограниченностью средств редактирования, а без него я не имею ни малейшего понятия, как этот алгоритм можно объяснить.
Читайте также: