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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица перехода состояний
Текущий состояние Вход	Государство А	Государство Б	Государство С
Вход Х	...	...	...
Ввод Y	...	Государство С	...
Ввод Z	...	...	...

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

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

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

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

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

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

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

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

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

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

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

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

Акцепторы

Рис. 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]

Датчики

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

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

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

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

Секвенсоры

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

Детерминизм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оптимизация

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

Выполнение

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

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

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

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

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

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

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

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

См. также

Ссылки

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

[1] Ван, Цзякунь (2019). Формальные методы в информатике . ЦРК Пресс. п. 34. ISBN 978-1-4987-7532-8 .

[2] «Конечные автоматы – блестящая математическая и научная вики» . блестящий.орг . Проверено 14 апреля 2018 г.

[Belzer-3] Белзер, Джек; Хольцман, Альберт Джордж; Кент, Аллен (1975). Энциклопедия компьютерных наук и технологий . Том. 25. США: CRC Press. п. 73. ИСБН 978-0-8247-2275-3 .

[Koshy-4] Jump up to: ^а ^б Коши, Томас (2004). Дискретная математика с приложениями . Академическая пресса. п. 762. ИСБН 978-0-12-421180-3 .

[⁇⁇⁇?-5] Райт, Дэвид Р. (2005). «Конечные автоматы» (PDF) . Примечания к классу CSC215 . Веб-сайт Дэвида Р. Райта, Университет штата Северная Каролина. Архивировано из оригинала (PDF) 27 марта 2014 г. Проверено 14 июля 2012 г.

[Keller2001-6] Jump up to: ^а ^б Келлер, Роберт М. (2001). «Классификаторы, акцепторы, преобразователи и секвенсоры» (PDF) . Информатика: от абстракции к реализации (PDF) . Колледж Харви Мадда. п. 480.

[7] Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-02988-8 .

[PoulyKohlas2012-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. ИЭПП ирландскийКонференция по сигналам и системам (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 г. .

[AndersonHead2006-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 года. Проверено 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

v т и Цифровая электроника
Components	Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU)
Theory	Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent
Design	Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine
Applications	Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature
Design issues	Metastability Runt pulse