Конечные автоматы являются мощным инструментом для работы. Компиляторы работает на основе конечных автоматов. Любой алгоритм которые вы пишете может быть представлен в виде конечного автомата.
В конечном автомате количесто состояний конечно, а результат его работа определяется по его конченому состоянию (Wikipedia). Существует несколько видов конечных автоматов:
Детерминированный кончечный автомат (ДКА)
Из любого состояние должен быть только один преход по символову, иначе этот автомат недерминирован. ДКА является самым удобным из всех конченых автоматов. Его удобнее всего обработаывать, всегда стараются свести задачу к построению ДКА. Но разобрать НКА и ε-НКА также необходимо.
Недетерминированный конечный автомат(НКА)
Предположим нам надо построить автомат, который принимает все строки, состоящие из символов [0, 1], где второй символ будет 0.
ε-Недетерминированный конечный автомат (ε-НКА)
ε-НКА очень похож на НКА, только теперь мы можем преходить по ε. Теперь ничего не считав, мы сможем перейти из одной вершины в другую. Принмает теже слова, что и предыдущий
Эквиалетность
Есть свойство у конченых автоматов — это их эквиалетность. ДКА НКА ε-НКА. Благодаря этому мы можем спокойно из ε-НКА сделать ДКА, это нам сильно пригодится.
Вкратце, разобрав какие бывают автоматы, мы можем перейти к более подробному изучению их реализации
Реализация
Обработка автомата
Как же можно проверить принимает ли данный кончечный автомат строку. Для ДКА все очевидно. Мы храним матрицу преходов, текущее состояние (когда мы ничего не считали, тек. сотояние = начальное состояние) и терминальные вершины. Считываем по одному символу, и переходим в состояние по матрице перехода.
Для НКА вместо текущего состояния мы храним множество текущих состояний. Разберем НКА данный выше.
Пусть мы хотим перейти по символу 0. Текущее множество состояний — множество, состоящее из одной вершины — начальной. У нас есть два прехода по символу 0 => множество состояний у нас будет 0, Q1>. Затем перейдем по символу 0. Из Q0 мы попадаем в Q0 и в Q1, из Q1 в Q2 => наше множество будет 0, q1, q2>.
Обработка ε-НКА похожа на обработку НКА. Предположим наше текущее множество S. Перед считываением следущего символа: для всех q ∈ S добавить в множество S вершину достигаемую из q по символу ε.
Детерминация автомата
Перевести автомат из ДКА в НКА легко. Нам просто ничего не нужно делать, т.к. ДКА это обобщенный случай НКА. Но что делать если мы хотим превести из ε-НКА в ДКА (НКА является обобшенным случаем ε-НКА). Этот процесс называется детерминацией автомата.
Начнем обоходить наш ε-НКА, например, DFS-ом. Вершиной графа является множество текущих состояний. Состояниями нового ДКА будут все вершины графа. При переходе к новой веришне мы выбираем символ по которому хотим перейти, и добавляем этот переход. Приведу псевдокод DFS-a для большой ясности:
Если в множестве есть терминальное состояние, то состояние нового ДКА будет тоже терминальным.
К сожалению число состояние нового ДКА будет расти экспоненциально, что не очень хорошо, т.к. это будет потреблять много памяти.
Алгоритм минимизации ДКА
Любой ДКА имеет эквиалетный ему ДКА с минимальным числом состояний. Как его «сжать»? Заметим, что неразличимые вершины мы можем соединить в одну. Что такое различимое состояние? Состояние p и q являются различимыми, если есть такое слово s, что преходя из вершины p по слову s мы попадаем в терминальное состояние, а из вершины q в не-терминальное, или наоборот.
1) Терминальное и не-терминальное состояние являются различимыми. Перейдем по пустому слову и окажемся в двух различимых состояниях. 2) Состояния a и b различимы. Если существуют состояния c и d, и из c есть переход по символу x в состояние a, а из веришны d есть переход по символу x в состояние b, то состояние a и b различимы.
Мы нашли все различимые состояния. Теперь нам надо «схлопнуть» все неразличимые.
Регулярные выражения
Регулярные варжения напрямую связаны с конечными автоматами. Введем некоторые обозначения: ∅ — пустое множество. ε — строка, которая не сожержит символов.
Пусть A и B регулярные выражения. L(A) и L(B) — кончечные языки, которые данные регулярные варжения задают.
Это основные операции прменимые к регулярным варжением. Можно всетрить и другие, но все они могут быть представлены операциями данными выше.
Вот представление основных операций регулярных выражений в виде ε-НКА.
Дале разбираем это выражение рекурсивным спуском и строим ε-НКА.
Чтобы обработать Регулярное выражение построим для ε-НКА, а потом получим из ε-НКА ДКА, который очень легко обрабатывать.
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.
Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.
Стартовое состояние — состояние откуда КА начинает свою работу.
Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.
Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.
НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.
Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.
Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.
Множества состояний — в один момент времени НКА может находится в нескольких состояниях.
Заключительное состояние обозначается двойным кругом.
В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.
Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.
Для преобразования НКА в ДКА используется алгоритм Томпсона. При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.
Конечные автоматы с магазинной памятью (pushdown automaton)
Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).
Удаление символа из стека — при любом переходе решается какой символ вытолкнуть, если на вершине стека не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стеке, то он добавляется вместе с добавляемыми символами.
Добавление символов в стек — при любом переходе решает какие символы добавить в стек.
Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.
ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.
Машина Тьюринга (Turing machine)
Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.
Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.
Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.
Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.
ДМТ эквивалентен НМТ, так, что они тоже не различаются.
Универсальная машина Тьюринга (universal Turing machine)
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
Автор: Сергей Холодилов The RSDN Group Источник: RSDN Magazine #2-2007
Опубликовано: 30.07.2007 Исправлено: 15.04.2009 Версия текста: 1.0
Недетерминированные конечные автоматы – одна из моделей, используемых в теории вычислений. Вряд ли всё это когда-нибудь пригодится вам «по жизни»… но, чёрт возьми, математика – это интересно! Во всяком случае, для меня. А если уж она хоть как-то с программированием связана, то интересна вдвойне.
Я не претендую на математическую строгость, получилось что-то типа «популярной математики для чайников»… Но надо же с чего-то начинать. А причём здесь орки – поймёте по ходу дела 🙂
Просто конечные автоматы
Скорее всего, все более-менее знают, что такое конечные автоматы. Проблема в том, что я, например, знаю три варианта: конечные автоматы Мура, конечные автоматы Мили и «просто» конечные автоматы. Поскольку дальше нам потребуется вполне конкретное определение, имеет смысл ввести его здесь.
Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:
И функционирующие следующим образом:
Возможно, более простым вам покажется следующее определение: детерминированным конечным автоматом называется такой автомат, в котором при любой данной последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. – прим.ред.
Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.
ПРИМЕЧАНИЕ
Это определение конечного автомата используется в теории вычислений. Автоматы Мура и Мили используются, в основном, при проектировании цифровой аппаратуры.
Конечные автоматы удобно изображать графически. На рисунке 1 приведён несложный ДКА, допускающий цепочки из 0 и 1, заканчивающиеся символом 0. Начальное состояние помечено входящей в него стрелочкой (да, этот здоровенный треугольник в душе – стрелочка), допускающее (в данном случае оно одно) – двойным кружком.
Рисунок 1. Простой детерминированный конечный автомат.
Второй вариант изображения автоматов – таблица переходов.
0
1
->
q 0
q 1
q 0
*
q 1
q 1
q 0
Таблица 1. Тот же самый конечный автомат.
По горизонтали отложены символы входного алфавита, по вертикали – состояния, начальное состояние отмечено стрелочкой, а допускающие – звёздочками. Этот способ изображения менее нагляден, и приведён только в качестве примера, использовать его «для дела» я не буду.
Добавляем недетерминированность
Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:
НКА тоже распознаёт цепочки символов, цепочка считается допустимой, если после её обработки множество состояний, в котором оказался автомат, содержит хотя бы одно допускающее. Таким образом, НКА также задаёт некоторый язык.
На рисунке 2 изображён простой НКА, допускающий цепочки из 0 и 1, заканчивающиеся на 00.
Рисунок 2. Простой недетерминированный конечный автомат.
Этот же автомат в виде таблицы:
0
1
->
q 0
q 1
Ø
*
q 2
Ø
Ø
Таблица 2. Тот же самый недетерминированный конечный автомат.
Разберёмся, как он работает.
Подход №1
Допустим, на вход автомату поступила цепочка «100100».
Автор: Сергей Холодилов The RSDN Group Источник: RSDN Magazine #2-2007
Опубликовано: 30.07.2007 Исправлено: 10.12.2016 Версия текста: 1.0
Недетерминированные конечные автоматы – одна из моделей, используемых в теории вычислений. Вряд ли всё это когда-нибудь пригодится вам «по жизни»… но, чёрт возьми, математика – это интересно! Во всяком случае, для меня. А если уж она хоть как-то с программированием связана, то интересна вдвойне.
Я не претендую на математическую строгость, получилось что-то типа «популярной математики для чайников»… Но надо же с чего-то начинать. А причём здесь орки – поймёте по ходу дела 🙂
Просто конечные автоматы
Скорее всего, все более-менее знают, что такое конечные автоматы. Проблема в том, что я, например, знаю три варианта: конечные автоматы Мура, конечные автоматы Мили и «просто» конечные автоматы. Поскольку дальше нам потребуется вполне конкретное определение, имеет смысл ввести его здесь.
Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:
И функционирующие следующим образом:
Возможно, более простым вам покажется следующее определение: детерминированным конечным автоматом называется такой автомат, в котором при любой данной последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. – прим.ред.
Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.
ПРИМЕЧАНИЕ
Это определение конечного автомата используется в теории вычислений. Автоматы Мура и Мили используются, в основном, при проектировании цифровой аппаратуры.
Конечные автоматы удобно изображать графически. На рисунке 1 приведён несложный ДКА, допускающий цепочки из 0 и 1, заканчивающиеся символом 0. Начальное состояние помечено входящей в него стрелочкой (да, этот здоровенный треугольник в душе – стрелочка), допускающее (в данном случае оно одно) – двойным кружком.
Рисунок 1. Простой детерминированный конечный автомат.
Второй вариант изображения автоматов – таблица переходов.
0
1
->
q 0
q 1
q 0
*
q 1
q 1
q 0
Таблица 1. Тот же самый конечный автомат.
По горизонтали отложены символы входного алфавита, по вертикали – состояния, начальное состояние отмечено стрелочкой, а допускающие – звёздочками. Этот способ изображения менее нагляден, и приведён только в качестве примера, использовать его «для дела» я не буду.
Добавляем недетерминированность
Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:
НКА тоже распознаёт цепочки символов, цепочка считается допустимой, если после её обработки множество состояний, в котором оказался автомат, содержит хотя бы одно допускающее. Таким образом, НКА также задаёт некоторый язык.
На рисунке 2 изображён простой НКА, допускающий цепочки из 0 и 1, заканчивающиеся на 00.
Рисунок 2. Простой недетерминированный конечный автомат.
Этот же автомат в виде таблицы:
0
1
->
q 0
q 1
Ø
*
q 2
Ø
Ø
Таблица 2. Тот же самый недетерминированный конечный автомат.
Разберёмся, как он работает.
Подход №1
Допустим, на вход автомату поступила цепочка «100100».
Подход №2
Менее формальное, но немного более наглядное представление обработки той же цепочки тем же автоматом изображено на рисунке 3.
Рисунок 3. Обработка цепочки 100100
В данном случае мы несколько удаляемся от определения НКА (множества состояний не представлены так явно). Картинка основана на следующей идее: каждый раз, когда по входному символу возможен переход в несколько состояний, порождается новая ветка вычислений, когда переходов нет – ветка «засыхает». Если хоть одна из «живых» веток ведёт в допускающее состояние – цепочка допущена.
В общем, подходы дают аналогичные результаты, за исключением одной мелочи. Слегка изменённый НКА, изображённый на рисунке 4, допускает любую цепочку символов <0, 1>, содержащую два нуля подряд. Если каждый раз честно порождать новую ветку, то при обработке цепочки «1001001….» получится дерево, изображённое на рисунке 5. Понятно, что две нижние ветки полностью совпадают (они представляют одинаковые состояния автомата, получают одинаковые входы, значит и результаты будут одинаковые), более того, каждый раз, когда в цепочке будет встречаться 00, будет порождаться ещё одна точно такая же ветка.
Рисунок 4. Немного изменённый НКА
Рисунок 5. Обработка цепочки 1001001.
Можно добавить слияние одинаковых веток, но это уменьшит наглядность. В подходе, основанном на множествах, слияние происходит автоматически – множество не может содержать два одинаковых элемента.
Подход №3
Наименее формальный подход к описанию работы НКА основан на том, что он «угадывает». Вернёмся к автомату на рисунке 2 и цепочке «100100».
То есть, фактически, мы взяли дерево из подхода №2, и обрезали все ветки, кроме одной – наиболее успешной.
… и эпсилон-переходы
Небольшое полезное расширение стандартного НКА – ε-НКА, или НКА с эпсилон-переходами.
«Эпсилон-переходом» называется переход между состояниями, который может быть выполнен автоматом «просто так», без входного символа. На графах и в таблицах такие переходы обычно помечаются символом ε.
ПРИМЕЧАНИЕ
В замечательной программе JFLAP, скриншоты из которой используются в качестве рисунков, ε-переходы почему-то обозначаются символом λ, но я нашёл в себе силы поправить картинки.
На рисунке 6 изображён пример ε-НКА.
Рисунок 6. НКА с ε-переходами.
Как это ни удивительно, но на этом немного странном примере продемонстрировано одно из наиболее полезных свойств ε-переходов – возможность простого объединения нескольких автоматов в один. В данном случае объединяемыми автоматами являются НКА, изображённые на рисунке 7, а результирующий автомат допускает цепочки, допустимые хотя бы одним из них.
Рисунок 7. Составные части автомата, показанного на рисунке 6.
Кроме того, обратите внимание, что никаких дополнительных ограничений на ε-переходы не накладывается. То есть:
В общем, граф/таблица переходов автомата выглядят так, как будто во входном алфавите появился ещё один символ – ε, а его работа так, будто в любом месте обрабатываемой цепочки (в начале, в конце, между символами) находится произвольное количество этих символов. При этом для каждого состояния есть как минимум один переход по ε – в себя.
… и более формально
Функцию eclose можно определить так:
А теперь мы можем строго определить функционирование ε-НКА.
И почему это круто
Допустим, вам нужен автомат, распознающий двоичные, десятичные и шестнадцатеричные числа в стандартном ассемблерном формате (я понимаю, что такие ситуации происходят в вашей жизни нечасто, но я и так сломал голову в поисках не слишком искусственного примера). То есть, допустимая строчка должна описываться одним из следующих утверждений:
Решение показано на рисунке 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 i » на «ε-замыкание состояния q i ». Вот эти места:
Доказательство идентичности описываемых автоматами языков аналогично доказательству для обычного НКА.
ПРИМЕЧАНИЕ
Таким образом, можно считать доказанным, что любой язык, описываемый ε-НКА, может быть описан обычным ДКА. А поскольку обратное очевидно (ДКА это просто частный случай ε-НКА), вычислительная мощность ДКА и ε-НКА совпадают.
Просто хотелось отдельно отметить этот важный теоретический результат 🙂
Алгоритм
Состояния ДКА
Такое количество состояний немного пугает, но, к счастью, часто подавляющее большинство состояний оказывается недостижимым (то есть, не существует последовательности переходов, которая приводит автомат в такое состояние из начального), поэтому их можно просто отбросить, и это никак не повлияет на описываемый ДКА язык.
Но часто – не значит всегда. Пример НКА, ДКА которого будет содержать 2 M-1 состояний, приведён на рисунке 10. Вставляя «в хвост» НКА дополнительные состояния, можно неограниченно увеличивать количество состояний ДКА.
Рисунок 10. Неудачный НКА.
Генерация ДКА
Возможны два подхода:
Мы пойдём вторым путём. Основная идея алгоритма:
Производительность
Но зато, после того как ДКА сгенерирован, он обрабатывает любой символ за константное время, а строчку длиной N – за O(N).
Заключение
Возможно (я на это надеюсь!), вам кажется, что всё описано недостаточно строго, или же что описано ужасающе мало. Этих и многих других недостатков лишена замечательная книжка «Введение в теорию автоматов, языков и вычислений», авторы Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман (издательство Вильямс, 2002). Очень рекомендую, правда, вряд ли вы её найдёте в магазинах, разве что на русском выпустят третье издание.
Значительно проще найти книгу «Классика программирования: алгоритмы, языки, автоматы, компиляторы», Мозговой М.В., Наука и Техника, 2006. Тоже хорошая книжка, она менее фундаментальна и строга, ближе к программированию, и содержит куски кода на C#.
Ну а играть с автоматами проще всего в программе JFLAP, которая уже упоминалась выше.
