Абстрактные конечные автоматы принято описывать в следующих терминах. Задано конечное множество символов X,которое называется (входным) алфавитом. Множество всех возможных цепочек (последовательностей, строк, слов), составленных из символов алфавита X, обозначается X*. Пустая последовательность символов обозначается X*.Если абстрактный вычислитель способен решить эту проблему для определенного языка L X* и произвольной строки X*, то говорят, что вычислитель В таком случае, если , то есть стартуя в начальном состоянии и обработав цепочку, автомат оказывается в одном из допускающих состояний, то говорят, что он допускает эту цепочку. Множество допускаемых цепочек образует язык L, распознаваемый ДКА: Класс языков, распознаваемых ДКА, называют регулярными языками. Известно, что он совпадает с классом языков, описываемых регулярными выражениями и автоматными грамматиками
Детерминированный конечный автомат-преобразователь. Для того чтобы наделить модель абстрактного конечного автомата способностью не только давать ответ типа да/нет, но и выполнять какие-то преобразования, в модель добавляют конечный алфавит выходных символов Z и функцию выхода ?Если функция выхода имеет вид X Y > Z, то вычислитель называется автоматом Мили, а если : Y > Z — автоматом Мура. Таким образом, рассматривается шестерка XYZy,,,,,??0. Она определяет автоматное отображение f : X* > Z* (преобразование, выполняемое автоматом) следующим образом:
Автоматные отображения — это отображения «без предсказания»: перерабатывая цепочку слева направо, они «не заглядывают вперед». Например, отображение, которое сопоставляет цепочке ее саму, записанную в обратном порядке, не является автоматным. Недетерминированный конечный автомат. Довольно часто используют модели, в которых считается, что автомат может на каждом такте находиться не в одном, а в нескольких состояниях одновременно. Известно, что недетерминизм не увеличивает вычислительной мощности модели и для каждого НКА существует эквивалентный (распознающий тот же язык) ДКА Автоматы со спонтанными переходами. С точки зрения программирования важным является случай, когда в автоматной модели допускается смена состояния, причиной которого не является внешнее воздействие. В моделях абстрактных автоматов такие переходы называют переходами, поскольку буква обычно резервируется для обозначения пустого слова — отсутствия какого-либо входного символа. Используют также эквивалентные термины: «спонтанный переход», «немотивированный переход», «переход по завершении». Из теории формальных языков известно, что допущение ?-переходов не расширяет класса распознаваемых языков автоматных моделей так же, как и допущение недетерминизма Таким образом, любой автомат с переходами может быть сведен к эквивалентному ДКА.В программных системах часто используются автоматные модели, в которых все переходы являются спонтанными (в пункте 1.4.3 такие модели названы активными). Отметим, что немотивированный переход, в общем случае, необязательно является безусловным. Спонтанность выражается в том, что переход совершается по инициативе самого автомата. При этом автомат может проверить истинность некоторого условия и принять решение о совершении перехода, исходя из результата проверки. В этом случае говорят, что переход помечен (или охраняется) условием. Еще одно значение спонтанных переходов для программирования состоит в том, что их использование позволяет считать традиционные блок-схемы (схемы алгоритмов) частным случаем диаграмм переходов автоматов. Действительно, блок-схема — это граф переходов, в котором из каждого состояния (кроме тех, которые соответствуют заключительным шагам алгоритма) исходит либо единственный безусловный ?-переход (рис. 1.7), либо несколько ?-переходов, помеченных одним или несколькими независимыми условиями. Обычно в блок-схемах множество переходов, помеченных независимыми условиями, изображают как сегментированный переход: условия проверяются не одновременно, а одно за другим. Пример приведен на рис. 1.8: на блок-схеме (слева) сначала проверяется «Условие 1», а затем, в случае его ложности, «Условие 2». На диаграмме переходов (справа) оба условия проверяются одновременно. Именно для блок-схем применяется термин «переход по завершении». Смысл этого термина состоит в том, что причиной перехода из текущего состояния в следующее является завершение выполнения действий, предписанных данному состоянию. Модели абстрактных конечных автоматов, описанные выше, пригодны лишь для распознавания регулярных языков. Однако существуют и используются нерегулярные языки. Наиболее употребительный пример — распространенные языки программирования. В случае если вычислительной мощности ДКА оказывается недостаточно, применяются различные расширения данной модели. Расширения производятся за счет добавления в модель дополнительной памяти того или иного вида. Автоматы с магазинной памятью. Автоматы с магазинной памятью (МП-автоматы) широко используются для синтаксического анализа. В этой модели к конечному автомату добавляется магазин (стек). В нем хранятся символы некоторого магазинного алфавита, который, в общем случае, не совпадает с входным алфавитом. На каждом такте работы автомат снимает один символ с вершины магазина и, в зависимости от его значения, переходит в новое состояние и заталкивает в стек некоторую строку магазинных символов. Такого механизма оказывается достаточно для распознавания контекстно-свободных языков — класса языков, в который попадает большая часть конструкций современных языков программирования. Так же как и конечные автоматы, МП-автоматы могут быть детерминированными и недетерминированными, иметь или не иметь ?-переходы. При этом, в отличие от конечных автоматов, соответствующие модификации МП-автоматов не являются вполне эквивалентными и описывают близкие, но различные подклассы класса контекстно-свободных языков. В частности, детерминированные МП-автоматы без спонтанных переходов распознают те контекстно-свободные языки, которые могут быть описаны синтаксически однозначной порождающей грамматикой. Переход МП-автомата — это отношение > на множестве конфигураций, которое определяется следующим образом: Отношение >* на множестве конфигураций определяется как рефлексивное транзитивное замыкание отношения >.Заметим, что для ДКА использовать понятие конфигурации (пары — состояние и остаток входа) можно, но в этом нет необходимости, поскольку Достижимость конфигураций полностью описывается расширенной функцией переходов. Кроме рассмотренных вычислителей подобную структуру (наличие устройства управления в виде ДКА и некоторого вида дополнительной памяти) имеют еще несколько абстрактных машин. Например, многоленточная машина Тьюринга и счетчиковые машины Только бесконечная дополнительная память (которая может хранить бесконечное множество значений) увеличивает вычислительную мощность абстрактной машины. Примерами являются стек МП-автомата и лента машины Тьюринга, приспособленные для хранения бесконечного числа различных строк w W*. Если же множество возможных значений памяти (обозначим его V ) конечно, то вычислитель всегда может быть преобразован в эквивалентный ДКА. Множество состояний этого ДКА будет декартовым произведением Y V множества состояний исходного вычислителя и множества значений его дополнительной памяти.