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

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

Классы автоматов

Конечный автомат ( FSM ) или конечный автомат ( FSA , множественное число: автоматы ), конечный автомат или просто конечный автомат — это математическая модель вычислений . Это абстрактная машина , которая в любой момент времени может находиться ровно в одном из конечного числа состояний . Конечный автомат может переходить из одного состояния в другое в ответ на некоторые входные данные ; переход из одного состояния в другое называется переходом . ^[1] Конечный автомат определяется списком его состояний, его начальным состоянием и входными данными, которые запускают каждый переход. Конечные автоматы бывают двух типов — детерминированные конечные автоматы и недетерминированные конечные автоматы . ^[2] Для любого недетерминированного конечного автомата можно построить эквивалентный детерминированный автомат.

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

Конечный автомат имеет меньшую вычислительную мощность, чем некоторые другие модели вычислений, такие как машина Тьюринга . ^[3] Различие в вычислительной мощности означает, что существуют вычислительные задачи, которые машина Тьюринга может выполнять, а автомат - нет. Это связано с тем, что память автомата ограничена количеством имеющихся у него состояний. Конечный автомат обладает той же вычислительной мощностью, что и машина Тьюринга, которая ограничена таким образом, что ее головка может выполнять только операции «чтения» и всегда должна двигаться слева направо. Автоматы изучаются в более общей области теории автоматов .

Пример: турникет с монетоприемником.

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

Турникет

Примером простого механизма, который можно смоделировать с помощью конечного автомата, является турникет . ^{[4] [5]} Турникет, используемый для контроля доступа в метро и аттракционы в парках развлечений, представляет собой ворота с тремя вращающимися рычагами на высоте талии, один поперек входа. Первоначально рычаги заблокированы, блокируя вход и не позволяя посетителям пройти. Внесение монеты или жетона в прорезь турникета разблокирует рычаги, позволяя пройти одному клиенту. После прохождения покупателя рычаги снова блокируются до тех пор, пока не будет вставлена ​​еще одна монета.

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

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

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

Концепции и терминология

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

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

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

Представительства

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

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

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

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

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

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

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

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

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

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

SDL включает базовые типы данных, называемые «абстрактными типами данных», язык действий и семантику выполнения, чтобы сделать конечный автомат исполняемым. ^{[ нужна цитата ]}

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

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

Применение

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

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

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

Акцепторы

Рис. 4: Принимающий автомат: анализ строки «хорошо».

Рис. 5: Изображение акцептанта; В этом примере показан тот, который определяет, имеет ли двоичное число четное количество нулей, где S ₁ — принимающее состояние , а S ₂ — непринимающее состояние .

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

Набор (возможно, бесконечный) набор последовательностей символов, называемый формальным языком , является регулярным языком, если существует некоторый акцептор, который принимает именно этот набор. Например, набор двоичных строк с четным числом нулей является регулярным языком (см. рис. 5), а набор всех строк, длина которых является простым числом, — нет. ^{[7] : 18, 71}

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

Проблема определения языка, принимаемого данным акцептором, является примером проблемы алгебраического пути , которая сама по себе является обобщением задачи о кратчайшем пути на графы с ребрами, взвешенными элементами (произвольного) полукольца . ^{[8] [9] [ жаргон ]}

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

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

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

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

Датчики

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

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

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

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

Машина Мура

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

Мучнистая машина

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

Секвенсоры

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

Детерминизм

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

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

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

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

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

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

Детерминированный конечный автомат или детерминированный акцептор с конечным состоянием представляет собой пятерку , где: ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$

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

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

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

Преобразователь с конечным состоянием представляет собой шестерку , где: ${\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}$

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

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

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

Оптимизация

Оптимизация автомата означает поиск машины с минимальным количеством состояний, выполняющей ту же функцию. Самый быстрый известный алгоритм, делающий это, — это алгоритм минимизации Хопкрофта . ^{[18] [19]} Другие методы включают использование таблицы импликаций или процедуры сокращения Мура. ^[20] Кроме того, ациклические FSA можно минимизировать за линейное время . ^[21]

Выполнение

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

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

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

В машине Медведева выход напрямую подключен к триггерам состояния, что минимизирует временную задержку между триггерами и выходом. ^{[22] [23]}

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

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

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

• Программирование на основе автоматов
• Конечный автомат, управляемый событиями
• Виртуальный конечный автомат
• Государственный шаблон проектирования

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

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

Смотрите также

• Абстрактные государственные машины
• Попеременный конечный автомат
• Коммуникационный конечный автомат
• Система контроля
• Таблица управления
• Таблицы решений
• РАЗРАБОТЧИКИ
• Скрытая модель Маркова
• сеть Петри
• Нажимной автомат
• Квантовый конечный автомат
• SCXML
• Полуавтомат
• Полугрупповое действие
• Последовательная логика
• Диаграмма состояний
• Синхронизация слова
• Полугруппа трансформации
• Переходная система
• Древовидный автомат
• Машина Тьюринга
• Конечный автомат UML

Рекомендации

1. Ван, Цзякунь (2019). Формальные методы в информатике . ЦРК Пресс. п. 34. ISBN 978-1-4987-7532-8.
2. "Конечные автоматы - блестящая математическая и научная вики" . блестящий.орг . Проверено 14 апреля 2018 г.
3. Белзер, Джек; Хольцман, Альберт Джордж; Кент, Аллен (1975). Энциклопедия компьютерных наук и технологий. Том. 25. США: CRC Press. п. 73. ИСБН 978-0-8247-2275-3.
4. Коши, Томас (2004). Дискретная математика с приложениями. Академическая пресса. п. 762. ИСБН 978-0-12-421180-3.
5. Райт, Дэвид Р. (2005). «Конечные автоматы» (PDF) . Примечания к классу CSC215 . Веб-сайт Дэвида Р. Райта, Университет штата Северная Каролина. Архивировано из оригинала (PDF) 27 марта 2014 г. Проверено 14 июля 2012 г.
6. Келлер, Роберт М. (2001). «Классификаторы, акцепторы, преобразователи и секвенсоры» (PDF) . Информатика: от абстракции к реализации (PDF) . Колледж Харви Мадда. п. 480.
7. Джон Э. Хопкрофт и Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления. Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-02988-8.
8. Пули, Марк; Кохлас, Юрг (2011). Общий вывод: объединяющая теория для автоматизированного рассуждения . Джон Уайли и сыновья. Глава 6. Алгебры оценки для задач пути, с. 223 в частности. ISBN 978-1-118-01086-0.
9. Яцек Йонци (июнь 2008 г.). «Задачи алгебраических путей» (PDF) . Архивировано из оригинала (PDF) 21 августа 2014 г. Проверено 20 августа 2014 г., п. 34
10. Фелкин, М. (2007). Гийе, Фабрис; Гамильтон, Ховард Дж. (ред.). Меры качества в интеллектуальном анализе данных — исследования в области вычислительного интеллекта . Том. 43. Шпрингер, Берлин, Гейдельберг. стр. 277–278. дои : 10.1007/978-3-540-44918-8_12. ISBN 978-3-540-44911-9.
11. Брутчек М., Бергер С., Франке М., Шварцбахер А., Беккер С.: Процедура структурного разделения для эффективного анализа IC. Ирландская конференция IET по сигналам и системам (ISSC 2008), стр. 18–23. Голуэй, Ирландия, 18–19 июня 2008 г. [1]
12. «Тивари, А. (2002). Формальная семантика и методы анализа для моделей потока состояний Simulink» (PDF) . Шри.com . Проверено 14 апреля 2018 г.
13. Хамон, Г. (2005). Денотационная семантика для Stateflow . Международная конференция по встраиваемому программному обеспечению. Джерси-Сити, Нью-Джерси: ACM. стр. 164–172. CiteSeerX 10.1.1.89.8817 . 
14. «Харел, Д. (1987). Визуальный формализм для сложных систем. Наука компьютерного программирования, 231–274» (PDF) . Архивировано из оригинала (PDF) 15 июля 2011 г. Проверено 7 июня 2011 г.
15. «Алур Р., Канаде А., Рамеш С. и Шашидхар К.К. (2008). Символический анализ для улучшения охвата моделирования моделей Simulink/Stateflow. Международная конференция по встроенному программному обеспечению (стр. 89–98). Атланта, Джорджия: ACM» (PDF) . Архивировано из оригинала (PDF) 15 июля 2011 г.
16. Блэк, Пол Э (12 мая 2008 г.). «Конечная машина». Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Архивировано из оригинала 13 октября 2018 года . Проверено 2 ноября 2016 г. .
17. Андерсон, Джеймс Эндрю; Хед, Томас Дж. (2006). Теория автоматов с современными приложениями. Издательство Кембриджского университета. стр. 105–108. ISBN 978-0-521-84887-9.
18. Хопкрофт, Джон Э. (1971). Алгоритм n log n для минимизации состояний в конечном автомате (PDF) (технический отчет). Том. CS-TR-71-190. Стэнфордский университет.^{[ постоянная мертвая ссылка ]}
19. Алмейда, Марко; Морейра, Нельма; Рейс, Роджерио (2007). О работе алгоритмов минимизации автоматов (PDF) (Технический отчет). Том. ДКК-2007-03. Университет Порто. Архивировано из оригинала (PDF) 17 января 2009 года . Проверено 25 июня 2008 г.
20. Эдвард Ф. Мур (1956). CE Шеннон и Дж. Маккарти (ред.). «Предполагаемые эксперименты на последовательных машинах». Анналы математических исследований . Издательство Принстонского университета. 34 : 129–153.Здесь: Теорема 4, стр.142.
21. Ревуз, Д. (1992). «Минимизация ациклических автоматов за линейное время». Теоретическая информатика . 92 : 181–189. дои : 10.1016/0304-3975(92)90142-3.
22. Кэслин, Хьюберт (2008). «Мили, Мур, Медведев и комбинаторные выходные биты». Проектирование цифровых интегральных схем: от архитектуры СБИС до изготовления КМОП . Издательство Кембриджского университета. п. 787. ИСБН 978-0-521-88267-5.
23. Слайды. Архивировано 18 января 2017 г. в Wayback Machine , Синхронные конечные автоматы; Дизайн и поведение , Университет прикладных наук Гамбурга , стр.18.
24. Ахо, Альфред В .; Сетхи, Рави ; Уллман, Джеффри Д. (1986). Составители: принципы, методы и инструменты (1-е изд.). Аддисон-Уэсли . ISBN 978-0-201-10088-4.

дальнейшее чтение

Общий

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

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

• Арбиб, Майкл А. (1969). Теории абстрактных автоматов (1-е изд.). Энглвуд Клиффс, Нью-Джерси: ISBN Prentice-Hall, Inc. 978-0-13-913368-8.
• Боброу, Леонард С.; Арбиб, Майкл А. (1974). Дискретная математика: прикладная алгебра для компьютерных и информационных наук (1-е изд.). Филадельфия: ISBN WB Saunders Company, Inc. 978-0-7216-1768-8.
• Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов (1-е изд.). Нью-Йорк: John Wiley and Sons, Inc., номер карточного каталога Библиотеки Конгресса 67-25924.
• Булос, Джордж; Джеффри, Ричард (1999) [1989]. Вычислимость и логика (3-е изд.). Кембридж, Англия: Издательство Кембриджского университета. ISBN 978-0-521-20402-6.
• Брукшир, Дж. Гленн (1989). Теория вычислений: формальные языки, автоматы и сложность . Редвуд-Сити, Калифорния: ISBN Benjamin/Cummings Publish Company, Inc. 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 . дои : 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-е изд.). Нью-Йорк: ISBN John Wiley and Sons, Inc. 978-0-471-08840-0.
• Маккласки, Э.Дж. (1965). Введение в теорию переключающих цепей (1-е изд.). Нью-Йорк: McGraw-Hill Book Company, Inc. Номер карточного каталога Библиотеки Конгресса 65-17394.
• Хилл, Фредрик Дж.; Петерсон, Джеральд Р. (1965). Введение в теорию переключающих цепей (1-е изд.). Нью-Йорк: Книжная компания McGraw-Hill. Каталожный номер карточки Библиотеки Конгресса 65-17394.

Конечные процессы цепи Маркова

«Мы можем думать о цепи Маркова как о процессе, который последовательно проходит через набор состояний s ₁ , s ₂ , …, 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 «Конечные цепи Маркова».

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

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