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

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

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

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

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

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

Пример: монетный турникет [ править ]

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

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

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

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

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

Понятия и терминология [ править ]

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

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

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

Представления [ править ]

Таблица состояний / событий [ править ]

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

Конечные автоматы UML [ править ]

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

Конечные автоматы SDL [ править ]

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

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

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

Диаграммы других состояний [ править ]

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

Использование [ править ]

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

Классификация [ править ]

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

Акцепторы [ править ]

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

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

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

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

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

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

Классификаторы [ править ]

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

Преобразователи [ править ]

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

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

Машина Мура

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

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

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

Секвенсоры [ править ]

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

Детерминизм [ править ]

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

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

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

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

Математическая модель [ править ]

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

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

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

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

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

Оптимизация [ править ]

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

Реализация [ править ]

Аппаратные приложения [ править ]

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

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

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

Программные приложения [ править ]

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

Общие [ править ]

• Сакарович, Жак (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-е изд.). Нью-Йорк: Джон Вили и сыновья, 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-е изд.). Нью-Йорк: ISBN Harper & Row, Publishers, Inc. 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-е изд.). Нью-Йорк: Джон Вили и сыновья, 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-е изд.). Нью-Йорк: Джон Вили и сыновья, Inc. Каталог карточек Библиотеки Конгресса № 67-25924.
• Кемени, Джон Дж .; Миркил, Хэзлтон; Снелл, Дж. Лори; Томпсон, Джеральд Л. (1959). Конечные математические структуры (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, Инк. Номер каталога карточек Библиотеки Конгресса 59-12841. Глава 6 «Конечные цепи Маркова».

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме конечного автомата .

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