Введение

Математическая модель вычислений

Конечный автомат (FSM) или конечный автомат состояния (FSA, множественное число: автоматы), конечный автомат, или просто машина состояний, является математической моделью вычислений. Это абстрактная машина, которая в любой момент времени может находиться ровно в одном из конечного числа состояний. Автомат может переходить из одного состояния в другое в ответ на входные данные; переход из одного состояния в другое называется переходом. Автомат определяется списком его состояний, начальным состоянием и входными данными, которые вызывают каждый переход. Автоматы бывают двух типов: детерминированные автоматы и недетерминированные автоматы. Для любого недетерминированного автомата можно построить эквивалентный детерминированный автомат. Поведение автоматов можно наблюдать во многих устройствах современного мира, которые выполняют предопределённую последовательность действий в зависимости от последовательности событий, с которыми они сталкиваются. Простые примеры: торговые автоматы, выдающие товар при внесении правильной комбинации монет; лифты, порядок остановок которых определяется запрошенными этажами; светофоры, меняющие последовательность работы при ожидании автомобилей; кодовые замки, требующие ввода последовательности цифр в правильном порядке. Автоматы имеют меньшую вычислительную мощность, чем некоторые другие модели вычислений, такие как машина Тьюринга. Это различие в вычислительной мощности означает, что существуют вычислительные задачи, которые машина Тьюринга может выполнить, а автомат – нет. Это связано с тем, что память автомата ограничена количеством его состояний. Автомат имеет ту же вычислительную мощность, что и машина Тьюринга, ограниченная таким образом, что её головка может выполнять только операции чтения и всегда должна двигаться слева направо. Автоматы изучаются в более общей области теории автоматов.

Пример: турниковый столб с монетой

Примером простого механизма, который можно смоделировать с помощью конечного автомата, является турникет. Турникет, используемый для контроля доступа в метро и к аттракционам в парках развлечений, представляет собой ворота с тремя вращающимися перекладинами на высоте пояса, одна из которых перекрывает вход. Изначально перекладины заблокированы, препятствуя входу и проходу посетителей. Опускание монеты или жетона в прорезь турникета разблокирует перекладины, позволяя одному человеку пройти. После того, как человек проходит, перекладины снова блокируются до тех пор, пока не будет вставлена другая монета. Рассматривая турникет как конечный автомат, он имеет два возможных состояния: Заблокирован и Разблокирован.

Приемники

Приемники (также называемые детекторами или распознавателями) выдают двоичный результат, указывающий, принимается ли полученный ввод. Каждое состояние приемника является либо принимающим, либо непринимающим. После получения всего ввода, если текущее состояние является принимающим, ввод принимается; в противном случае он отклоняется. Обычно ввод представляет собой последовательность символов (знаков); действия не используются. Начальное состояние также может быть принимающим, в этом случае приемник принимает пустую строку. Пример на рисунке 4 демонстрирует приемник, принимающий строку "nice". В этом приемнике единственным принимающим состоянием является состояние 7. (Возможно, бесконечный) набор последовательностей символов, называемый формальным языком, является регулярным языком, если существует приемник, который принимает именно этот набор. Например, множество двоичных строк с четным числом нулей является регулярным языком (см. рис. 5), а множество всех строк, длина которых является простым числом, – нет. Приемник также можно рассматривать как определяющий язык, который содержит все строки, принятые приемником, но не содержит отвергнутые; этот язык принимается приемником. По определению, языки, принимаемые приемниками, являются регулярными языками. Задача определения языка, принимаемого данным приемником, является частным случаем задачи об алгебраическом пути – обобщением задачи о кратчайшем пути для графов с ребрами, взвешенными элементами (произвольного) полукольца. Пример принимающего состояния показан на рис. 5: детерминированный конечный автомат (ДКА), который определяет, содержит ли двоичная входная строка четное число нулей. S1 (который также является начальным состоянием) указывает на состояние, в котором было введено четное число нулей. Следовательно, S1 является принимающим состоянием. Этот приемник завершит работу в принимающем состоянии, если двоичная строка содержит четное число нулей (включая любую двоичную строку, не содержащую нулей). Примеры строк, принимаемых этим приемником: ε (пустая строка), 1, 11, 00, 010, 1010, 10110 и т. д.

Классификаторы

Классификаторы — это обобщение акцепторов, выдающих n-арный выход, где n строго больше двух.

Секвенсоры

Секвенсоры (также называемые генераторами) являются подклассом акцепторов и трансдусеров, имеющих однобуквенный входной алфавит. Они генерируют только одну последовательность, которую можно рассматривать как выходную последовательность выходов акцептора или трансдусера.

Альтернативная семантика

Существуют и другие наборы семантики, доступные для представления конечных автоматов. Например, существуют инструменты для моделирования и проектирования логики для встраиваемых контроллеров. Они объединяют иерархические автоматы (которые обычно имеют более одного текущего состояния), графы потоков и таблицы истинности в единый язык, что приводит к другому формализму и набору семантики. Эти диаграммы, как и оригинальные автоматы Хареля, поддерживают иерархически вложенные состояния, ортогональные области, действия состояний и действия переходов.

Оптимизация

Оптимизация FSM означает нахождение машины с минимальным количеством состояний, реализующей ту же функцию. Самый быстрый известный алгоритм для этого – алгоритм минимизации Хопкрофта. Другие методы включают использование таблицы подвыводов или процедуру редукции Мура. Кроме того, ациклические FSA могут быть минимизированы за линейное время.

Аппаратные приложения

В цифровой схеме конечный автомат (FSM) может быть построен с использованием программируемого логического устройства, программируемого логического контроллера, логических элементов и триггеров или реле. В частности, аппаратная реализация требует регистра для хранения переменных состояния, блока комбинационной логики, определяющего переход между состояниями, и второго блока комбинационной логики, определяющего выходные сигналы конечного автомата. Одним из классических примеров аппаратной реализации является контроллер Ричардса. В машине Медведева выход напрямую подключен к триггерам состояния, что минимизирует задержку между триггерами и выходом. Путем кодирования состояний автоматы с низким энергопотреблением могут быть оптимизированы для снижения потребления энергии.

Машины и компиляторы с конечным состоянием

Конечные автоматы часто используются на начальном этапе компиляторов языков программирования. Такой фронтэнд может состоять из нескольких автоматов с конечным числом состояний, реализующих лексический анализатор и парсер. Начиная с последовательности символов, лексический анализатор строит последовательность лексем языка (таких как зарезервированные слова, литералы и идентификаторы), из которых парсер строит синтаксическое дерево. Лексический анализатор и парсер обрабатывают регулярную и контекстно-свободную части грамматики языка программирования.

Общий

Вагнер, Ф., "Моделирование программного обеспечения с помощью конечных автоматов: практический подход", Auerbach Publications, 2006, ITU T, Рекомендация Z.100 Язык спецификаций и описаний (SDL)
Самек, М., Практические диаграммы состояний в C/C++, CMP Books, 2002, Самек, М., Практические диаграммы состояний UML в C/C++, 2-е издание, Newnes, 2008, Гарднер, Т., Продвинутое управление состояниями, 2007
Кассандрас, К., Лафортун, С., "Введение в дискретные системы событий". Kluwer, 1999, Тимоти Кам, Синтез конечных автоматов: функциональная оптимизация. Kluwer Academic Publishers, Бостон, 1997, Тициано Вилла, Синтез конечных автоматов: логическая оптимизация. Kluwer Academic Publishers, Бостон, 1997,
Кэрролл, Дж., Лонг, Д., Теория конечных автоматов с введением в формальные языки. Prentice Hall, Энглвуд Клиффс, 1989. Кохави, З., Теория переключений и конечных автоматов. McGraw Hill, 1978. Гилл, А., Введение в теорию конечных автоматов. McGraw Hill, 1962. Гинзбург, С., Введение в теорию математических машин. Addison Wesley, 1962.

Процессы конечных цепей Маркова

Мы можем рассматривать цепь Маркова как процесс, последовательно переходящий через набор состояний s1, s2, ..., sr. Если она находится в состоянии si, то на следующем шаге переходит в состояние sj с вероятностью pij. Эти вероятности можно представить в виде матрицы переходов (Кемени (1959), с. 384). Конечные процессы цепей Маркова также известны как сдвиги конечного типа. Глава 6 "Конечные цепи Маркова".