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

редактировать

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

Классы автоматов (При нажатии на каждый слой открывается статья на эту тему)

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

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

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

Содержание

1 Пример: монетный турникет
2 Понятия и терминология
3 Представления
- 3.1 Таблица состояний / событий
- 3.2 Конечные автоматы UML
- 3.3 Конечные автоматы SDL
- 3.4 Другие диаграммы состояний
4 Использование
5 Классификация
- 5.1 Акцепторы
- 5.2 Классификаторы
- 5.3 Преобразователи
- 5.4 Секвенсоры
- 5.5 Детерминизм
6 Альтернативная семантика
7 Математическая модель
8 Оптимизация
9 Реализация
- 9.1 Аппаратные приложения
- 9.2 Программные приложения
- 9.3 Конечные машины и компиляторы
10 См. Также
11 Ссылки
12 Дополнительная литература
- 12.1 Общие положения
- 12.2 Конечные автоматы (теория автоматов) в теоретической информатике
- 12.3 Автоматы с абстрактными состояниями в теоретической информатике
- 12.4 Машинное обучение с использованием алгоритмов конечных состояний
- 12.5 Аппаратная инженерия: минимизация состояний и синтез последовательных схем
- 12.6 Конечная цепь Маркова процессы
13 Внешние ссылки

Пример: монетный турникет

Диаграмма состояний турникета

Турникет

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

Турникет, рассматриваемый как конечный автомат, имеет два возможных состояния: Заблокирован и Разблокирован . Есть два возможных входа, которые влияют на его состояние: вставка монеты в прорезь (coin ) и нажатие на рычаг (push ). В заблокированном состоянии нажатие на руку не имеет никакого эффекта; независимо от того, сколько раз вводится вход push, он остается в заблокированном состоянии. Вставка монеты, то есть предоставление автомату ввода coin, меняет состояние с Locked на Unlocked . В разблокированном состоянии добавление дополнительных монет не имеет никакого эффекта; то есть предоставление дополнительных входных данных coin не изменяет состояние. Тем не менее, клиент, проталкивая рычаги, давая на вход push, возвращает состояние обратно на Заблокировано .

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

Текущее состояние	Вход	Следующее состояние	Выход
Заблокировано	coin	Разблокировано	Разблокирует турникет, чтобы покупатель мог пройти через него.
Заблокировано	push	Locked	None
Unlocked	coin	Unlocked	None
Unlocked	push	Заблокировано	Когда клиент протолкнется, турникет запирается.

Конечный автомат турникета также может быть представлен направленным графом, который называется диаграммой состояний (см. Выше). Каждое состояние представлено узлом (кружок). Ребра (стрелки) показывают переходы из одного состояния в другое. Каждая стрелка помечена входом, который запускает этот переход. Вход, который не вызывает изменения состояния (например, вход coin в состоянии Unlocked ), представлен круговой стрелкой, возвращающейся в исходное состояние. Стрелка в узле Заблокировано от черной точки указывает, что это начальное состояние.

Понятия и терминология

Состояние - это описание состояния системы, ожидающей выполнения перехода. Переход - это набор действий, которые должны выполняться при выполнении условия или при получении события. Например, при использовании аудиосистемы для прослушивания радио (система находится в состоянии «радио») получение стимула «следующая» приводит к переходу к следующей станции. Когда система находится в состоянии «CD», «следующий» стимул приводит к переходу к следующей дорожке. Одинаковые стимулы запускают разные действия в зависимости от текущего состояния.

В некоторых представлениях конечного автомата также можно связать действия с состоянием:

действие входа: выполняется при входе в состояние, и
действие выхода: выполнено при выходе из состояния.

Представления

Рис. 1 Пример диаграммы состояний UML (тостер)

Рис. 2 Пример конечного автомата SDL

Рис. 3 Пример простого конечного автомата

Таблица состояний / событий

Используются несколько типов таблиц переходов между состояниями. Наиболее распространенное представление показано ниже: комбинация текущего состояния (например, B) и ввода (например, Y) показывает следующее состояние (например, C). Полная информация о действии не описана в таблице напрямую и может быть добавлена только с помощью сносок. Определение конечного автомата, включающее полную информацию о действиях, возможно с использованием таблиц состояний (см. Также виртуальный конечный автомат ).

Таблица переходов между состояниями
Текущее. состояниеВход	Состояние A	Состояние B	Состояние C
Вход X	...	...	...
Вход Y	...	Состояние C	...
Вход Z	...	...	...

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

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

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

Язык спецификаций и описания является стандартом из ITU, который включает графические символы для описания действий при переходе:

отправить событие
получить событие
запустить таймер
отменить таймер
запустить другой параллельный конечный автомат
решение

SDL встраивает базовые типы данных, называемые «абстрактными типами данных», язык действий и семантику выполнения, чтобы сделать конечный автомат исполняемым.

Диаграммы других состояний

Существует большое количество вариантов для представления конечного автомата, такого как показанный на рисунке 3.

Использование

В дополнение к их использованию при моделировании реактивного представленные здесь системы, конечные машины играют важную роль во многих областях, включая электротехнику, лингвистику, информатику, философию, биологию, математика, программирование видеоигр и логика. Конечные автоматы - это класс автоматов, изучаемый в теории автоматов и теории вычислений. В информатике конечные автоматы широко используются для моделирования поведения приложений, проектирования аппаратных цифровых систем, программной инженерии, компиляторов, сетей. протоколы, а также изучение вычислений и языков.

Классификация

Конечные автоматы можно подразделить на акцепторы, классификаторы, преобразователи и секвенсоры.

Акцепторы

Рис. 4: Acceptor FSM: анализ строки "nice".

Рис. 5: изображение акцептора; в этом примере показано, как определить, имеет ли двоичное число четное количество нулей, где S 1 - это принимающее состояние, а S 2 - это не принимающее состояние.

Принимающие (также называемые детекторами или распознавателями ) производят двоичный вывод, указывая, принят ли принятый ввод. Каждое состояние акцептора либо принимает, либо не принимает. После получения всех входных данных, если текущее состояние является состоянием приема, вход принимается; в противном случае он отклоняется. Как правило, вводом является последовательность символов (знаков); действия не используются. Начальное состояние также может быть состоянием приема, и в этом случае акцептор принимает пустую строку. Пример на рисунке 4 показывает акцептор, который принимает строку "nice". В этом акцепторе единственное принимающее состояние - это состояние 7.

(возможно, бесконечный) набор последовательностей символов, называемый формальным языком, является обычным языком, если есть некий акцептор, который принимает именно этот набор. Например, набор двоичных строк с четным числом нулей является обычным языком (см. Рис. 5), в то время как набор всех строк, длина которых является простым числом, не является.

Акцептор может также можно описать как определение языка, который будет содержать каждую строку, принимаемую акцептором, но ни одну из отклоненных; этот язык принимается принимающей стороной. По определению, языки, принимаемые акцепторами, являются обычными языками.

. Проблема определения языка, принимаемого данным акцептором, является примером - самого по себе обобщения проблемы кратчайшего пути к графы с ребрами, взвешенными элементами (произвольного) полукольца.

Пример принимающего состояния показан на рис.5: детерминированный конечный автомат (DFA), который определяет, есть ли двоичная входная строка содержит четное количество нулей.

S1(который также является начальным состоянием) указывает состояние, в котором было введено четное количество нулей. S 1, следовательно, является состоянием приема. Этот акцептор завершит работу в состоянии принятия, если двоичная строка содержит четное количество нулей (включая любую двоичную строку, не содержащую нулей). Примеры строк, принимаемых этим акцептором: ε (пустая строка ), 1, 11, 11..., 00, 010, 1010, 10110 и т. Д.

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

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

Преобразователи

Рис. 6 FSM преобразователя: пример модели Мура

Рис. 7 Конечный автомат преобразователя: пример модели Мили

Преобразователи выдают выходной сигнал на основе заданного входа и / или состояния с использованием действий. Они используются для управляющих приложений и в области вычислительной лингвистики.

В управляющих приложениях различают два типа:

машина Мура: FSM использует только действия входа, т. Е. Вывод зависит только от состояния. Преимущество модели Мура - упрощение поведения. Рассмотрим дверь лифта. Конечный автомат распознает две команды: «command_open» и «command_close», которые запускают изменение состояния. Действие входа (E :) в состоянии «Открытие» запускает двигатель, открывающий дверь, действие входа в состоянии «Закрытие» запускает двигатель в другом направлении, закрывая дверь. Состояния «Открыто» и «Закрыто» останавливают двигатель при полном открытии или закрытии. Они сигнализируют внешнему миру (например, другим конечным автоматам) о ситуации: «дверь открыта» или «дверь закрыта».

Машина Мили: FSM также использует входные действия, т. Е. Выход зависит от входа и состояние. Использование автомата Мили часто приводит к уменьшению количества состояний. В примере на рисунке 7 показан автомат Мили, реализующий то же поведение, что и в примере Мура (поведение зависит от реализованной модели выполнения конечного автомата и будет работать, например, для виртуального FSM, но не для события . -управляемый FSM ). Есть два действия ввода (I :): «запустить двигатель, чтобы закрыть дверь, если прибывает command_close» и «запустить двигатель в другом направлении, чтобы открыть дверь, если прибывает command_open». Промежуточные состояния «открытие» и «закрытие» не показаны.

Секвенсоры

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

Детерминизм

Еще одно различие между детерминированным (DFA ) и недетерминированные (NFA, GNFA ) автоматы. В детерминированном автомате каждое состояние имеет ровно один переход для каждого возможного входа. В недетерминированном автомате вход может привести к одному, более чем одному или отсутствию перехода для данного состояния. Алгоритм построения набора мощности может преобразовать любой недетерминированный автомат в (обычно более сложный) детерминированный автомат с идентичной функциональностью.

Конечный автомат с одним состоянием называется «комбинаторным автоматом». Он разрешает действия только при переходе в состояние. Эта концепция полезна в тех случаях, когда требуется несколько конечных автоматов для совместной работы, и когда удобно рассматривать чисто комбинаторную часть как форму конечного автомата, подходящую для инструментов проектирования.

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

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

Математическая модель

В соответствии с общей классификацией, найдены следующие формальные определения.

Детерминированный конечный автомат или детерминированный конечный автомат - это пятерка $(Σ, S, s 0, δ, F) {\ displaystyle (\ Sigma, S, s_ {0}, \ delta, F)}$ $(\ Sigma, S, s_ {0}, \ delta, F)$ , где:

$Σ {\ displaystyle \ Sigma}$ $\ Sigma$ - входной алфавит (конечный непустой набор символов);
$S {\ displaystyle S}$ $S$ - конечный непустой набор состояний;
$s 0 {\ displaystyle s_ {0}}$ $s_{0}$ - начальное состояние, элемент $S {\ displaystyle S}$ $S$ ;
$δ {\ displaystyle \ delta}$ $\ delta$ - функция перехода между состояниями: $δ: S × Σ → S {\ displaystyle \ delta: S \ times \ Sigma \ rightarrow S}$ $\ delta: S \ times \ Sigma \ rightarrow S$ (в недетерминированном конечном автомате это будет $δ: S × Σ → P (S) {\ Displaystyle \ delta: S \ times \ Sigma \ rightarrow {\ mathcal {P}} (S)}$ $\ delta: S \ times \ Sigma \ rightarrow {\ mathcal {P}} (S)$ , то есть $δ {\ displaystyle \ delta}$ $\ delta$ будет возвращает набор состояний);
$F {\ displaystyle F}$ $F$ - набор конечных состояний, (возможно, пустое) подмножество $S {\ displaystyle S}$ $S$ .

для обоихДля детерминированных и недетерминированных автоматов принято позволять $δ {\ displaystyle \ delta}$ $\ delta$ быть частичной функцией, т. е. $δ (s, x) {\ displaystyle \ delta (s, x)}$ ${\ displaystyle \ delta (s, x)}$ необязательно определять для каждой комбинации $s ∈ S {\ displaystyle s \ in S}$ ${\ displaystyle s \ in S}$ и $Икс ∈ Σ {\ Displaystyle х \ в \ Sigma}$ $x \ in \ Sigma$ . Если конечный автомат $M {\ displaystyle M}$ $M$ находится в состоянии $s {\ displaystyle s}$ $s$ , следующим символом будет $x {\ displaystyle x }$ $x$ и $δ (s, x) {\ displaystyle \ delta (s, x)}$ ${\ displaystyle \ delta (s, x)}$ не определено, тогда $M {\ displaystyle M}$ $M$ может объявить об ошибке (т.е. отклонить ввод). Это полезно в определениях общих конечных автоматов, но менее полезно при преобразовании машины. Некоторые алгоритмы в их стандартной форме могут потребовать общих функций.

Конечный автомат имеет ту же вычислительную мощность, что и машина Тьюринга, которая ограничена таким образом, что его голова может выполнять только операции «чтения» и всегда должна двигаться слева направо.. То есть каждый формальный язык, принятый конечным автоматом, принимается такой ограниченной машиной Тьюринга, и наоборот.

A Конечный преобразователь является следовательной $(Σ, Γ, S, s 0, δ, ω) {\ displaystyle (\ Sigma, \ Gamma, S, s_ {0}, \ delta, \ omega)}$ $(\ Sigma, \ Gamma, S, s_ {0}, \ delta, \ omega)$ , где:

$Σ {\ displaystyle \ Sigma}$ $\ Sigma$ - входной алфавит (конечный непустой набор символов);
$Γ {\ displaystyle \ Gamma}$ $\ Gamma$ - выходной алфавит (конечный непустой набор символов);
$S {\ displaystyle S}$ $S$ - конечный непустой набор состояний;
$s 0 {\ displaystyle s_ { 0}}$ $s_{0}$ - начальное состояние, элемент $S {\ displaystyle S}$ $S$ ;
$δ {\ displaystyle \ delta}$ $\ delta$ - функция перехода между состояниями: $δ: S × Σ → S {\ displaystyle \ delta: S \ times \ Sigma \ rightarrow S}$ $\ delta: S \ times \ Sigma \ rightarrow S$ ;
$ω {\ displaystyle \ omega}$ $\ omega$ - функция вывода.

Если функция вывода зависит от состояния и символа ввода ( $ω: S × Σ → Γ {\ displaystyle \ omega: S \ ti mes \ Sigma \ rightarrow \ Gamma}$ $\ omega: S \ times \ Sigma \ rightarrow \ Gamma$ ), это определение соответствует модели Мили и может быть смоделировано как машина Мили. Если функция вывода зависит только от состояния ( $ω: S → Γ {\ displaystyle \ omega: S \ rightarrow \ Gamma}$ $\ omega: S \ rightarrow \ Gamm a$ ), это определение соответствует модели Мура и может быть смоделировано как машина Мура. Конечный автомат без функции вывода вообще известен как полуавтомат или система перехода.

. Если мы не будем принимать во внимание первый выходной символ автомата Мура, $ω (s 0) {\ displaystyle \ omega (s_ {0})}$ ${\ displaystyle \ omega (s_ {0})}$ , то его можно легко преобразовать в эквивалентную машину Мили для вывода, установив функцию вывода для каждого перехода Мили (т. е. пометив каждый край) выходной символ, заданный для состояния Мура назначения. Обратное преобразование менее прямолинейно, поскольку состояние машины Мили может иметь разные выходные метки на входящих переходах (краях). Каждое такое состояние должно быть разделено на несколько состояний машины Мура, по одному для каждого выходного символа инцидента.

Оптимизация

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

Реализация

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

Рис. 9 Принципиальная схема для 4-битного TTL счетчика, типа конечного автомата

В цифровой схеме конечный автомат может быть построен с использованием программируемое логическое устройство, программируемый логический контроллер, логические вентили и триггеры или реле. Более конкретно, для аппаратной реализации требуется регистр для хранения переменных состояния, блок комбинационной логики, который определяет переход состояния, и второй блок комбинационной логики, который определяет вывод FSM. Одной из классических аппаратных реализаций является контроллер Ричардса.

. В машине Медведева выход напрямую связан с триггерами состояния, что минимизирует временную задержку между триггерами и выходом.

Через Кодирование состояния для конечных автоматов с низким энергопотреблением может быть оптимизировано для минимизации энергопотребления.

Программные приложения

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

Конечные автоматы и компиляторы

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

См. Также

Ссылки

Дальше r чтение

Генерал

Сакарович, Жак (2009). Элементы теории автоматов. Перевод с французского Рувима Томаса. Издательство Кембриджского университета. ISBN 978-0-521-84425-3. Zbl 1188.68177.
Вагнер, Ф., «Программное обеспечение для моделирования с конечными автоматами: практический подход», Публикации Ауэрбаха, 2006 г., ISBN 0-8493-8086-3.
ITU-T, Рекомендация Z.100 Язык спецификации и описания (SDL)
Самек, М., Практические диаграммы состояний на C / C ++, CMP Книги, 2002, ISBN 1-57820-110-1.
Самек, М., Практические диаграммы состояний UML на C / C ++, 2-е издание, Newnes, 2008, ISBN 0-7506-8706-1.
Гарднер, Т., Advanced State Management, 2007
Кассандрас, С., Лафортюн, С., "Введение в дискретные системы событий". Kluwer, 1999, ISBN 0-7923-8609-4.
Тимоти Кам, Синтез конечных автоматов: функциональная оптимизация. Kluwer Academic Publishers, Бостон, 1997, ISBN 0-7923-9842-4
Тициано Вилла, Синтез конечных автоматов: логическая оптимизация. Kluwer Academic Publishers, Бостон, 1997 г., ISBN 0-7923-9892-0
Кэрролл, Дж., Лонг, Д., Теория конечных автоматов с введением к формальным языкам. Prentice Hall, Englewood Cliffs, 1989.
Кохави, З., Теория переключений и конечных автоматов. Макгроу-Хилл, 1978.
Гилл А. Введение в теорию конечных автоматов. McGraw-Hill, 1962.
Гинзбург, С., Введение в математическую теорию машин. Addison-Wesley, 1962.

Конечные автоматы (теория автоматов) в теоретической информатике

Арбиб, Майкл А. (1969). Теории абстрактных автоматов (1-е изд.). Энглвуд Клиффс, штат Нью-Джерси: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
Bobrow, Leonard S.; Арбиб, Майкл А. (1974). Дискретная математика: прикладная алгебра для компьютерных и информационных наук (1-е изд.). Филадельфия: W. B. Saunders Company, Inc. ISBN 978-0-7216-1768-8.
Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов (1-е изд.). Нью-Йорк: John Wiley and Sons, Inc. Каталог карточек Библиотеки Конгресса № 67-25924.
Булос, Джордж; Джеффри, Ричард (1999) [1989]. Вычислимость и логика (3-е изд.). Кембридж, Англия: Издательство Кембриджского университета. ISBN 978-0-521-20402-6.
Брукшир, Дж. Гленн (1989). Теория вычислений: формальные языки, автоматы и сложность. Редвуд-Сити, Калифорния: Benjamin / Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
Дэвис, Мартин; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность, языки и логика: основы теоретической информатики (2-е изд.). Сан-Диего: Academic Press, Harcourt, Brace Company. ISBN 978-0-12-206382-4.
Хопкрофт, Джон; Ульман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Месса для чтения: Эддисон-Уэсли. ISBN 978-0-201-02988-8.
Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Месса для чтения: Эддисон-Уэсли. ISBN 978-0-201-44124-6.
Хопкин, Дэвид; Мосс, Барбара (1976). Автоматы. Нью-Йорк: Эльзевиер Северная Голландия. ISBN 978-0-444-00249-5.
Козен, Декстер К. (1997). Автоматы и вычислимость (1-е изд.). Нью-Йорк: Springer-Verlag. ISBN 978-0-387-94907-9.
Льюис, Гарри Р. ; Пападимитриу, Христос Х. (1998). Элементы теории вычислений (2-е изд.). Река Аппер Сэдл, Нью-Джерси: Прентис-Холл. ISBN 978-0-13-262478-7.
Линц, Питер (2006). Формальные языки и автоматы (4-е изд.). Садбери, Массачусетс: Джонс и Бартлетт. ISBN 978-0-7637-3798-6.
Минский, Марвин (1967). Вычисление: конечные и бесконечные машины (1-е изд.). Нью-Джерси: Прентис-Холл.
Пападимитриу, Христос (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 978-0-201-53082-7.
Пиппенгер, Николас (1997). Теории вычислимости (1-е изд.). Кембридж, Англия: Издательство Кембриджского университета. ISBN 978-0-521-55380-3.
Роджер, Сьюзен; Финли, Томас (2006). JFLAP: пакет интерактивных формальных языков и автоматов (1-е изд.). Садбери, Массачусетс: Джонс и Бартлетт. ISBN 978-0-7637-3834-1.
Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). Бостон Масса: технология курса Томсона. ISBN 978-0-534-95097-2.
Вуд, Дерик (1987). Теория вычислений (1-е изд.). Нью-Йорк: Harper Row, Publishers, Inc. ISBN 978-0-06-047208-5.

Абстрактные машины состояний в теоретической информатике

Гуревич Юрий (июль 2000 г.). «Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы» (PDF). Транзакции ACM по вычислительной логике. 1 (1): 77–111. CiteSeerX 10.1.1.146.3017. DOI : 10.1145 / 343369.343384. S2CID 2031696.

Машинное обучение с использованием алгоритмов с конечным числом состояний

Митчелл, Том М. (1997). Машинное обучение (1-е изд.). Нью-Йорк: WCB / McGraw-Hill Corporation. ISBN 978-0-07-042807-2.

Аппаратная инженерия: минимизация состояния и синтез последовательных схем

Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов (1-е изд.). Нью-Йорк: John Wiley and Sons, Inc. Каталог карточек Библиотеки Конгресса, номер 67-25924.
Бут, Тейлор Л. (1971). Цифровые сети и компьютерные системы (1-е изд.). Нью-Йорк: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
McCluskey, E.J. (1965). Введение в теорию коммутационных цепей (1-е изд.). Нью-Йорк: McGraw-Hill Book Company, Inc. Каталог карточек Библиотеки Конгресса № 65-17394.
Hill, Fredrick J.; Петерсон, Джеральд Р. (1965). Введение в теорию коммутационных цепей (1-е изд.). Нью-Йорк: Книжная компания Макгроу-Хилл. Каталог карточек Библиотеки Конгресса, номер 65-17394.

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

«Мы можем думать о цепи Маркова как о процессе, который последовательно проходит через набор состояний s 1, s 2,…, s r.… Если он находится в состоянии s i, он переходит к следующей остановке в состояние s j с вероятностью p ij. Эти вероятности могут быть представлены в виде матрицы переходов »(Кемени (1959), стр. 384)

Также известны процессы конечных цепей Маркова. как подмены конечного типа.

Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов (1-е изд.). Нью-Йорк: John Wiley and Sons, Inc. Каталог карточек Библиотеки Конгресса номер 67-25924.
Кемени, Джон Дж.; Миркил, Хэзлтон; Снелл, Дж. Лори; Томпсон, Джеральд Л. (1959). Конечные математические структуры (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. Каталог карточек Библиотеки Конгресса, номер 59-12841. Глава 6 «Конечные цепи Маркова».

Внешние ссылки

На Викискладе есть средства массовой информации, связанные с Конечный автомат.

Конечный автомат в Керли
Моделирование поведения простого ИИ с использованием конечного автомата Пример использования в видеоиграх
Бесплатно On- Строчный словарь вычислений описание конечных автоматов
Словарь алгоритмов и структур данных NIST описание конечных автоматов
Краткий обзор типов конечных автоматов, сравнение теоретических аспектов Конечные автоматы Мили, Мура, Харела и UML.