Конечные автоматы

Введение

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

В конечном автомате количесто состояний конечно, а результат его работа определяется по его конченому состоянию (Wikipedia).
Существует несколько видов конечных автоматов:

Детерминированный кончечный автомат (ДКА)

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

Недетерминированный конечный автомат(НКА)

Предположим нам надо построить автомат, который принимает все строки, состоящие из символов [0, 1], где второй символ будет 0.

ε-Недетерминированный конечный автомат (ε-НКА)

ε-НКА очень похож на НКА, только теперь мы можем преходить по ε. Теперь ничего не считав, мы сможем перейти из одной вершины в другую.

Принмает теже слова, что и предыдущий

Эквиалетность

Есть свойство у конченых автоматов — это их эквиалетность. ДКА НКА ε-НКА. Благодаря этому мы можем спокойно из ε-НКА сделать ДКА, это нам сильно пригодится.

Вкратце, разобрав какие бывают автоматы, мы можем перейти к более подробному изучению их реализации

Реализация

Обработка автомата

Как же можно проверить принимает ли данный кончечный автомат строку.
Для ДКА все очевидно. Мы храним матрицу преходов, текущее состояние (когда мы ничего не считали, тек. сотояние = начальное состояние) и терминальные вершины. Считываем по одному символу, и переходим в состояние по матрице перехода.

Для НКА вместо текущего состояния мы храним множество текущих состояний. Разберем НКА данный выше.

Пусть мы хотим перейти по символу 0. Текущее множество состояний — множество, состоящее из одной вершины — начальной. У нас есть два прехода по символу 0 => множество состояний у нас будет 0, Q₁>. Затем перейдем по символу 0. Из Q₀ мы попадаем в Q₀ и в Q₁, из Q₁ в Q₂ => наше множество будет 0, q₁, q₂>.

Обработка ε-НКА похожа на обработку НКА. Предположим наше текущее множество 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’.

Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.

Детерминированные конечные автоматы (deterministic finite automaton)

Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.

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

Недетерминированные конечные автоматы (nondeterministic finite automaton)

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

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

Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.

Множества состояний — в один момент времени НКА может находится в нескольких состояниях.

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

В стартовом состоянии у нас текущим состоянием является <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

Недетерминированные конечные автоматы – одна из моделей, используемых в теории вычислений. Вряд ли всё это когда-нибудь пригодится вам «по жизни»… но, чёрт возьми, математика – это интересно! Во всяком случае, для меня. А если уж она хоть как-то с программированием связана, то интересна вдвойне.

Я не претендую на математическую строгость, получилось что-то типа «популярной математики для чайников»… Но надо же с чего-то начинать. А причём здесь орки – поймёте по ходу дела 🙂

Просто конечные автоматы

Скорее всего, все более-менее знают, что такое конечные автоматы. Проблема в том, что я, например, знаю три варианта: конечные автоматы Мура, конечные автоматы Мили и «просто» конечные автоматы. Поскольку дальше нам потребуется вполне конкретное определение, имеет смысл ввести его здесь.

Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:

И функционирующие следующим образом:

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

Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.