- PVSM.RU - https://www.pvsm.ru -
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ 'a', из состояния 1 в состояние 2, если символ 'b'.
Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.
Стартовое состояние — состояние откуда КА начинает свою работу.
Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.
Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.
НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.
// Ячейка массива состоящая из: текущее_состояние, считаный_символ, следующее_состояние.
struct state {
unsigned char current;
signed char sym; // signed, для обозначения свободного перехода как -1.
unsigned char next;
};
// Таблица переходов для НКА на примере 2
struct state machine[] = {
{0, 'a', 1},
{1, 'a', 1},
{2, 'a', 1},
{1, 'b', 2},
{2, 'c', 3}
};
Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.
Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.
Множества состояний — в один момент времени НКА может находится в нескольких состояниях.
В стартовом состоянии у нас текущим состоянием является {1}, при входном символе 'b' у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа 'b' текущим состоянием является множество {1, 2}.
Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии {2, 4}.
Для преобразования НКА в ДКА используется алгоритм Томпсона [1].
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского [2].
Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стэка (я понимаю, что память тоже конечна).
Удаление символа из стэка — при любом переходе решается какой символ вытолкнуть, если на вершине стэка не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стэке, то он добавляется вместе с добавляемыми символами.
Добавление символов в стэк — при любом переходе решает какие символы добавить в стэк.
Виды:
Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стэка.
ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.
Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.
Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.
Этот МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.
Выполнение:
ДМТ эквивалентен НМТ, так, что они тоже не различаются.
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
Недостатки:
На этом введение в автоматы закончено, теперь вы можете продолжить изучать дальнейший материал сами.
Литература:
Автор: Evgeny Proshin
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/279963
Ссылки в тексте:
[1] алгоритм Томпсона: https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9D%D0%9A%D0%90_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%94%D0%9A%D0%90,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%BE%D0%BC%D0%BF%D1%81%D0%BE%D0%BD%D0%B0
[2] алгоритм Бржозовского: http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D1%80%D0%B6%D0%BE%D0%B7%D0%BE%D0%B2%D1%81%D0%BA%D0%BE%D0%B3%D0%BE
[3] «Теория вычислений для программистов», Том Стюарт: https://www.amazon.com/Understanding-Computation-Machines-Impossible-Programs/dp/1449329276/ref=sr_1_5?s=books&ie=UTF8&qid=1525978527&sr=1-5&refinements=p_27%3ATom+Stuart
[4] Источник: https://habr.com/post/358304/?utm_source=habrahabr&utm_medium=rss&utm_campaign=358304
Нажмите здесь для печати.