Конечный автомат - Finite-state machine

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

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

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

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

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

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

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

Турникет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Акцепторы

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

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

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

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

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

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

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

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

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

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

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

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

Рис.7 Преобразователь FSM: пример модели Мили

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

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

Машина Мура

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

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

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

Секвенсоры

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

Детерминизм

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

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

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

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

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

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

Детерминированный конечный автомат или детерминированный конечно-акцептор является пятикратно , где: ${\ 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}$

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

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

Конечно-преобразователь является шестикратный , где: ${\ 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}$

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

Оптимизация

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

Реализация

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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

Общий

• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Издательство Кембриджского университета . ISBN 978-0-521-84425-3. Zbl  1188.68177 .
• Вагнер, Ф., «Программное обеспечение для моделирования с конечными автоматами: практический подход», Auerbach Publications, 2006, ISBN  0-8493-8086-3 .
• ITU-T, Рекомендация Z.100 Язык спецификации и описания (SDL)
• Самек М., Практические диаграммы состояний на C / C ++ , CMP Books, 2002, ISBN  1-57820-110-1 .
• Самек М., Практические диаграммы состояний UML на C / C ++, 2-е издание , Newnes, 2008, ISBN  0-7506-8706-1 .
• Гарднер Т., Продвинутое государственное управление , 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
• Кэрролл Дж., Лонг Д. Теория конечных автоматов с введением в формальные языки . Прентис Холл, Энглвудские скалы, 1989.
• Кохави З. Теория переключений и конечных автоматов . Макгроу-Хилл, 1978.
• Гилл А. Введение в теорию конечных автоматов . Макгроу-Хилл, 1962 год.
• Гинзбург С. Введение в математическую теорию машин . Аддисон-Уэсли, 1962.

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

• Арбиб, Майкл А. (1969). Теории абстрактных автоматов (1-е изд.). Энглвуд Клиффс, Нью-Джерси: ISBN Prentice-Hall, Inc. 978-0-13-913368-8.
• Bobrow, Леонард S .; Арбиб, Майкл А. (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 . 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-е изд.). Нью-Йорк: ISBN John Wiley and Sons, Inc. 978-0-471-08840-0.
• Маккласки, EJ (1965). Введение в теорию коммутационных цепей (1-е изд.). Нью-Йорк: McGraw-Hill Book Company, Inc. Каталог карточек Библиотеки Конгресса № 65-17394.
• Хилл, Фредрик Дж .; Петерсон, Джеральд Р. (1965). Введение в теорию коммутационных цепей (1-е изд.). Нью-Йорк: Книжная компания Макгроу-Хилл. Каталог карточек Библиотеки Конгресса № 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-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, Инк. Номер каталога карточек Библиотеки Конгресса 59-12841. Глава 6 «Конечные цепи Маркова».

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

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