Теория автоматов

Изучение абстрактных машин и автоматов.

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

Автомат, описанный этой диаграммой состояний, запускается в состоянии S1 _и меняет состояния, следуя стрелкам, отмеченным 0 или 1, в соответствии с входными символами по мере их поступления. Двойной кружок обозначает S1 _как принимающее состояние. Поскольку все пути от S ₁ до самого себя содержат четное количество стрелок, отмеченных 0, этот автомат принимает строки, содержащие четное количество нулей.

Теория автоматов — это изучение абстрактных машин и автоматов , а также вычислительных задач , которые можно решить с их помощью. Это теория теоретической информатики , тесно связанная с математической логикой . Слово «автоматы» происходит от греческого слова αὐτόματος, что означает «самодействующий, своевольный, самодвижущийся». Автомат (во множественном числе автоматы) — абстрактное самоходное вычислительное устройство, автоматически выполняющее заданную последовательность операций. Автомат с конечным числом состояний называется конечным автоматом (FA) или конечным автоматом (FSM). На рисунке справа показан конечный автомат , который представляет собой известный тип автомата. Этот автомат состоит из состояний (изображенных на рисунке кружками) и переходов (изображенных стрелками). Когда автомат видит входной символ, он осуществляет переход (или переход) в другое состояние в соответствии со своей функцией перехода , которая принимает предыдущее состояние и текущий входной символ в качестве аргументов.

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

История

Теория абстрактных автоматов была развита в середине 20 в. в связи с конечными автоматами . ^[1] Теория автоматов изначально считалась разделом теории математических систем , изучающим поведение систем с дискретными параметрами. Ранние работы по теории автоматов отличались от предыдущих работ по системам тем, что для описания информационных систем использовалась абстрактная алгебра , а не дифференциальное исчисление для описания материальных систем. ^[2] Теория преобразователя с конечным состоянием разрабатывалась разными исследовательскими сообществами под разными названиями. ^[3] Более ранняя концепция машины Тьюринга также была включена в дисциплину вместе с новыми формами автоматов с бесконечным состоянием, такими как автоматы с выталкиванием .

В 1956 году была опубликована книга « Исследования автоматов» , в которой собраны работы таких ученых, как Клод Шеннон , У. Росс Эшби , Джон фон Нейман , Марвин Мински , Эдвард Ф. Мур и Стивен Коул Клини . ^[4] С публикацией этого тома «теория автоматов стала относительно автономной дисциплиной». ^[5] Книга включала описание Клини набора регулярных событий или регулярных языков , а также относительно стабильную меру сложности в программах машины Тьюринга Шеннона. ^[6] В том же году Ноам Хомский описал иерархию Хомского , соответствие между автоматами и формальными грамматиками , ^[7] и Росс Эшби опубликовал «Введение в кибернетику» , доступный учебник, объясняющий автоматы и информацию с использованием базовой теории множеств .

Исследование линейных ограниченных автоматов привело к теореме Майхилла-Нерода ^[8] , которая дает необходимое и достаточное условие регулярности формального языка и точный подсчет числа состояний в минимальной машине для этого языка. Лемма о накачке для регулярных языков , также полезная в доказательствах регулярности, была доказана в этот период Майклом О. Рабином и Даной Скотт , наряду с вычислительной эквивалентностью детерминированных и недетерминированных конечных автоматов. ^[9]

В 1960-х годах появился корпус алгебраических результатов, известных как «теория структуры» или «теория алгебраической декомпозиции», которые касались реализации последовательных машин из меньших машин путем соединения. ^[10] Хотя любой конечный автомат можно смоделировать с помощью универсального набора вентилей , для этого требуется, чтобы схема моделирования содержала циклы произвольной сложности. Теория структуры имеет дело с реализуемостью машин «без петель». ^[5] Теория вычислительной сложности также сформировалась в 1960-х годах. ^{[11] [12]} К концу десятилетия теория автоматов стала рассматриваться как «чистая математика информатики». ^[5]

Автоматы

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

Неофициальное описание

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

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

Формальное определение

Автомат

Автомат формально можно представить пятеркой , где: ${\displaystyle M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle }$

• ${\displaystyle \Sigma }$— конечное множество символов , называемое входным алфавитом автомата,
• ${\displaystyle \Gamma }$— другой конечный набор символов, называемый выходным алфавитом автомата,
• ${\displaystyle Q}$представляет собой совокупность состояний ,
• ${\displaystyle \delta }$- это функция следующего состояния или функция перехода, отображающая пары состояние-вход в состояния-преемники, ${\displaystyle \delta :Q\times \Sigma \to Q}$
• ${\displaystyle \lambda }$— это функция следующего вывода , отображающая пары состояние-вход на выходы. ${\displaystyle \lambda :Q\times \Sigma \to \Gamma }$

Если конечен, то является конечным автоматом . ^[5] ${\displaystyle Q}$ ${\displaystyle M}$

Введите слово

Автомат считывает конечную строку символов , где , которая называется входным словом . Множество всех слов обозначается . ${\displaystyle a_{1}a_{2}...a_{n}}$ ${\displaystyle a_{i}\in \Sigma }$ ${\displaystyle \Sigma ^{*}}$

Бегать

Последовательность состояний , где такова, что for , представляет собой запуск автомата по входу, начиная с состояния . Другими словами, сначала автомат находится в начальном состоянии и получает входные данные . Для каждого следующего во входной строке автомат выбирает следующее состояние в соответствии с функцией перехода до тех пор, пока не будет прочитан последний символ , оставляя машину в конечном состоянии выполнения . Аналогично на каждом шаге автомат выдает выходной символ в соответствии с выходной функцией . ${\displaystyle q_{0},q_{1},...,q_{n}}$ ${\displaystyle q_{i}\in Q}$ ${\displaystyle q_{i}=\delta (q_{i-1},a_{i})}$ ${\displaystyle 0<i\leq n}$ ${\displaystyle a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ ${\displaystyle q_{0}}$ ${\displaystyle q_{0}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle \delta (q_{i-1},a_{i})}$ ${\displaystyle a_{n}}$ ${\displaystyle q_{n}}$ ${\displaystyle \lambda (q_{i-1},a_{i})}$

Функция перехода индуктивно расширяется для описания поведения машины при вводе целых входных слов. Для пустой строки , для всех состояний и для строк где — последний символ и — (возможно, пустая) остальная часть строки, . ^[10] Функция вывода может быть расширена аналогичным образом до , что дает полный вывод машины при запуске по слову из состояния . ${\displaystyle \delta }$ ${\displaystyle {\overline {\delta }}:Q\times \Sigma ^{*}\to Q}$ ${\displaystyle \varepsilon }$ ${\displaystyle {\overline {\delta }}(q,\varepsilon )=q}$ ${\displaystyle q}$ ${\displaystyle wa}$ ${\displaystyle a}$ ${\displaystyle w}$ ${\displaystyle {\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)}$ ${\displaystyle \lambda }$ ${\displaystyle {\overline {\lambda }}(q,w)}$ ${\displaystyle w}$ ${\displaystyle q}$

Акцептор

Чтобы изучить автомат с помощью теории формальных языков , автомат можно рассматривать как акцептор , заменяя выходной алфавит и функцию и ${\displaystyle \Gamma }$ ${\displaystyle \lambda }$

• ${\displaystyle q_{0}\in Q}$, назначенное начальное состояние и
• ${\displaystyle F}$, набор состояний (т.е. ), называемых состояниями принятия . ${\displaystyle Q}$ ${\displaystyle F\subseteq Q}$

Это позволяет определить следующее:

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

Слово является принимающим словом для автомата, если , то есть если после потребления всей строки автомат находится в состоянии принятия. ${\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ ${\displaystyle {\overline {\delta }}(q_{0},w)\in F}$ ${\displaystyle w}$

Признанный язык

Язык, распознаваемый автоматом, — это совокупность всех слов, принимаемых автоматом . ^[13] ${\displaystyle L\subseteq \Sigma ^{*}}$ ${\displaystyle L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}}$

Узнаваемые языки

Распознаваемые языки — это набор языков, распознаваемых некоторым автоматом. Для конечных автоматов распознаваемыми языками являются регулярные языки . Для разных типов автоматов распознаваемые языки разные.

Варианты определений автоматов

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

Вход

• Конечный ввод : автомат, который принимает только конечные последовательности символов. Приведенное выше вводное определение охватывает только конечные слова.
• Бесконечный ввод : автомат, который принимает бесконечные слова ( ω-слова ). Такие автоматы называются ω-автоматами .
• Ввод дерева : входными данными может быть дерево символов, а не последовательность символов. В этом случае после чтения каждого символа автомат считывает все последующие символы во входном дереве. Говорят, что автомат делает одну копию самого себя для каждого преемника, и каждая такая копия начинает работать на одном из символов-последователей из состояния в соответствии с отношением перехода автомата. Такой автомат называется древовидным автоматом .
• Ввод бесконечного дерева  : два вышеуказанных расширения можно комбинировать, чтобы автомат считывал древовидную структуру с (не)конечными ветвями. Такой автомат называется автоматом бесконечного дерева .

состояния

• Одно состояние : автомат с одним состоянием, также называемый комбинационной схемой , выполняет преобразование, которое может реализовать комбинационную логику . ^[10]
• Конечные состояния : автомат, который содержит только конечное число состояний.
• Бесконечные состояния : автомат, который может не иметь конечного или даже счетного числа состояний. Чтобы дать таким машинам конечные описания, можно использовать различные виды абстрактной памяти.
• Память стека : автомат также может содержать некоторую дополнительную память в виде стека, в который можно помещать и извлекать символы. Этот тип автомата называется автоматом с выталкиванием .
• Память очереди : Автомат может иметь память в виде очереди . Такая машина называется машиной очереди и является Тьюринг-полной.
• Ленточная память : входы и выходы автоматов часто описываются как ленты ввода и вывода . Некоторые машины имеют дополнительные рабочие ленты , включая машину Тьюринга , линейный ограниченный автомат и преобразователь лог-пространства .

Функция перехода

• Детерминированный : для данного текущего состояния и входного символа, если автомат может перейти только в одно и только одно состояние, то это детерминированный автомат .
• Недетерминированный : автомат, который после считывания входного символа может перейти в любое из нескольких состояний в соответствии с его отношением перехода. Термин «функция перехода» заменяется отношением перехода: автомат недетерминированным образом решает перейти к одному из разрешенных вариантов. Такие автоматы называются недетерминированными автоматами .
• Чередование : эта идея очень похожа на древовидные автоматы, но ортогональна. Автомат может запустить несколько своих копий для одного и того же следующего символа чтения. Такие автоматы называются альтернирующими автоматами . Чтобы принять входные данные, условие принятия должно быть удовлетворено во всех запусках таких копий .
• Двусторонность : автоматы могут считывать вводимые данные слева направо или им может быть разрешено перемещаться вперед и назад по вводу, аналогично машине Тьюринга . Автоматы, которые могут двигаться вперед и назад на входе, называются двусторонними конечными автоматами .

Условие приемки

• Принятие конечных слов : То же, что описано в неформальном определении выше.
• Принятие бесконечных слов : ω-автомат не может иметь конечных состояний, поскольку бесконечные слова никогда не заканчиваются. Скорее, принятие слова определяется путем рассмотрения бесконечной последовательности посещенных состояний во время прогона.
• Вероятностное принятие : автомату не обязательно строго принимать или отклонять входные данные. Он может принять входные данные с некоторой вероятностью от нуля до единицы. Например, квантовые конечные автоматы, геометрические автоматы и метрические автоматы имеют вероятностное принятие.

Различные комбинации указанных выше вариантов дают множество классов автоматов.

Теория автоматов — это предмет, изучающий свойства различных типов автоматов. Например, о данном типе автоматов изучаются следующие вопросы.

• Какой класс формальных языков распознается автоматами того или иного типа? (Узнаваемые языки)
• Закрыты ли определенные автоматы относительно объединения, пересечения или дополнения формальных языков? (Свойства замыкания)
• Насколько выразителен тип автоматов с точки зрения распознавания класса формальных языков? И их относительная выразительная сила? (Языковая иерархия)

Теория автоматов также изучает существование или отсутствие каких-либо эффективных алгоритмов для решения задач, подобных следующему списку:

• Принимает ли автомат хотя бы одно входное слово? (проверка пустоты)
• Можно ли преобразовать данный недетерминированный автомат в детерминированный автомат без изменения распознаваемого языка? (Определение)
• Какой наименьший автомат распознает данный формальный язык? ( Минимизация )

Виды автоматов

Ниже приводится неполный список типов автоматов.

Дискретные, непрерывные и гибридные автоматы.

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

Иерархия с точки зрения полномочий

Ниже представлена ​​неполная иерархия полномочий различных типов виртуальных машин. Иерархия отражает вложенные категории языков, которые могут принимать машины. ^[14]

Приложения

Каждая модель теории автоматов играет важную роль в нескольких прикладных областях. Конечные автоматы используются в обработке текста , компиляторах и проектировании аппаратного обеспечения . Контекстно-свободная грамматика (CFG) используется в языках программирования и искусственном интеллекте. Первоначально CFG использовались при изучении человеческих языков . Клеточные автоматы используются в области искусственной жизни , наиболее известным примером является «Игра жизни » Джона Конвея . Некоторые другие примеры, которые можно объяснить с помощью теории автоматов в биологии, включают модели роста и пигментации моллюсков и сосновых шишек. Идя дальше, некоторые ученые отстаивают теорию, предполагающую, что вся Вселенная вычисляется неким дискретным автоматом. Идея возникла в работах Конрада Цузе и была популяризирована в Америке Эдвардом Фредкиным . Автоматы появляются и в теории конечных полей : множество неприводимых многочленов , которые можно записать как композицию многочленов второй степени, на самом деле является регулярным языком. ^[15] Другая проблема, для решения которой можно использовать автоматы, — это индукция регулярных языков .

Симуляторы автоматов

Симуляторы автоматов — это педагогические инструменты, используемые для преподавания, изучения и исследования теории автоматов. Симулятор автомата принимает на вход описание автомата, а затем моделирует его работу для произвольной входной строки. Описание автомата можно ввести несколькими способами. Автомат можно определить на символьном языке , его спецификацию можно ввести в заранее заданной форме, или диаграмму его переходов можно нарисовать, щелкнув и перетащив мышь. Хорошо известные симуляторы автоматов включают Turing's World, JFLAP, VAS, TAGS и SimStudio. ^[16]

Связь с теорией категорий

Можно определить несколько различных категорий автоматов ^[17] , следуя классификации автоматов на разные типы, описанной в предыдущем разделе. Математическая категория детерминированных автоматов, последовательных машин или последовательных автоматов и машин Тьюринга с гомоморфизмами автоматов , определяющими стрелки между автоматами, является декартовой замкнутой категорией , ^[18] она имеет как категориальные пределы , так и копределы . Гомоморфизм автоматов отображает пятерку автомата A _i на пятерку другого автомата A _j . Гомоморфизмы автоматов также можно рассматривать как преобразования автоматов или как гомоморфизмы полугрупп , когда пространство состояний S автомата определяется как полугруппа S _g . Моноиды также считаются подходящей средой для автоматов в моноидальных категориях . ^{[19] [20] [21]}

Категории переменных автоматов

Можно также определить переменный автомат в смысле Норберта Винера в его книге « Человеческое использование человеческих существ» через эндоморфизмы . Тогда можно показать, что такие гомоморфизмы переменных автоматов образуют математическую группу. Однако в случае недетерминированных или других сложных видов автоматов последний набор эндоморфизмов может стать переменным автоматным группоидом . Поэтому в самом общем случае категории переменных автоматов любого вида являются категориями группоидов или категориями группоидов. При этом категория обратимых автоматов тогда является 2-категорией , а также подкатегорией 2-категории группоидов или категорией группоидов. ${\displaystyle A_{i}\to A_{i}}$

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

• Булево дифференциальное исчисление

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

1. Махони, Майкл С. «Структуры вычислений и математическая структура природы». Резерфордский журнал . Проверено 7 июня 2020 г.
2. Бут, Тейлор (1967). Последовательные машины и теория автоматов . Нью-Йорк: Джон Уайли и сыновья. п. 1-13. ISBN 0-471-08848-Х.
3. Эшби, Уильям Росс (15 января 1967). «Место мозга в мире природы» (PDF) . Течения в современной биологии . 1 (2): 95–104. дои : 10.1016/0303-2647(67)90021-4. PMID  6060865. Архивировано из оригинала (PDF) 4 июня 2023 г. Проверено 29 марта 2021 г.: «Теории, в настоящее время хорошо развитые, о «конечном автомате» (Гилл, 1962), о «бесшумном преобразователе» (Шеннон и Уивер, 1949), о «системе, определяемой состоянием» (Эшби, 1952). и «последовательной цепи» по существу гомологичны».
4. Эшби, WR; и другие. (1956). CE Шеннон; Дж. Маккарти (ред.). Исследования автоматов . Принстон, Нью-Джерси: Издательство Принстонского университета.
5. Арбиб, Майкл (1969). Теории абстрактных автоматов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл.
6. Ли, Мин; Пол, Витаний (1997). Введение в колмогоровскую сложность и ее приложения . Нью-Йорк: Springer-Verlag. п. 84.
7. Хомский, Ноам (1956). «Три модели описания языка» (PDF) . IRE Транзакции по теории информации . 2 (3): 113–124. дои : 10.1109/TIT.1956.1056813. S2CID  19519474. Архивировано (PDF) из оригинала 07 марта 2016 г.
8. Нерод, А. (1958). «Линейные автоматные преобразования». Труды Американского математического общества . 9 (4): 541. doi : 10.1090/S0002-9939-1958-0135681-9 .
9. Рабин, Майкл ; Скотт, Дана (апрель 1959 г.). «Конечные автоматы и проблемы их решения» (PDF) . Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114. Архивировано из оригинала 14 декабря 2010 г.{{cite journal}}: CS1 maint: неподходящий URL ( ссылка )
10. Хартманис, Дж .; Стернс, RE (1966). Алгебраическая структурная теория последовательных машин . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл.
11. Хартманис, Дж.; Стернс, RE (1964). «Вычислительная сложность рекурсивных последовательностей» (PDF) .
12. Фортнау, Лэнс; Гомер, Стив (2002). «Краткая история сложности вычислений» (PDF) .
13. Мур, Кристофер (31 июля 2019 г.). «Автоматы, языки и грамматики». arXiv : 1907.12713 [cs.CC].
14. Ян, Сон Ю. (1998). Введение в формальные языки и машинные вычисления. Сингапур: World Scientific Publishing Co. Pte. ООО, стр. 155–156. ISBN 978-981-02-3422-5.
15. Феррагути, А.; Микели, Г.; Шнайдер, Р. (2018), Неприводимые композиции полиномов второй степени над конечными полями имеют регулярную структуру , Ежеквартальный журнал математики, том. 69, Oxford University Press, стр. 1089–1099, arXiv : 1701.06040 , doi : 10.1093/qmath/hay015, S2CID  3962424
16. Чакраборти, П.; Саксена, ПК; Катти, CP (2011). «Пятьдесят лет автоматического моделирования: обзор». ACM Inroads . 2 (4): 59–70. дои : 10.1145/2038876.2038893. S2CID  6446749.
17. Иржи Адамек и Вера Трнкова . 1990. Автоматы и алгебры в категориях . Kluwer Academic Publishers: Дордрехт и Прага.
18. Мак Лейн, Сондерс (1971). Категории для работающего математика . Нью-Йорк: Спрингер. ISBN 978-0-387-90036-0.
19. http://www.math.cornell.edu/~worthing/asl2010.pdf Джеймс Уортингтон.2010.Определение, забывание и автоматы в моноидальных категориях. Ежегодное собрание ASL в Северной Америке, 17 марта 2010 г.
20. Агиар, М. и Махаджан, С.2010. «Моноидальные функторы, виды и алгебры Хопфа» .
21. Месегер, Дж., Монтанари, У.: 1990 Сети Петри являются моноидами. Информация и вычисления 88 : 105–155.

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

• Джон Э. Хопкрофт ; Раджив Мотвани ; Джеффри Д. Уллман (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Пирсон Образование. ISBN 978-0-201-44124-6.
• Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN 978-0-534-94728-6.Часть первая: Автоматы и языки, главы 1–2, стр. 29–122. Раздел 4.1: Разрешимые языки, стр. 152–159. Раздел 5.1: Неразрешимые проблемы теории языка, стр. 172–183.
• Элейн Рич (2008). Автоматы, вычислимость и сложность: теория и приложения. Пирсон. ISBN 978-0-13-228806-4.
• Саломаа, Арто (1985). Вычисления и автоматы . Энциклопедия математики и ее приложений. Том. 25. Издательство Кембриджского университета . ISBN 978-0-521-30245-6. Збл  0565.68046.
• Андерсон, Джеймс А. (2006). Теория автоматов с современными приложениями . При участии Тома Хэда. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-61324-8. Збл  1127.68049.
• Конвей, Дж. Х. (1971). Регулярная алгебра и конечные машины . Серия Математики Чепмена и Холла. Лондон: Чепмен и Холл . Збл  0231.94041.
• Джон М. Хоуи (1991) Автоматы и языки , ISBN Clarendon Press 0-19-853424-8 MR 1254435 
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Издательство Кембриджского университета . ISBN 978-0-521-84425-3. Збл  1188.68177.
• Джеймс П. Шмайзер; Дэвид Т. Барнард (1995). Создание порядка анализа сверху вниз с анализом снизу вверх . Эльзевир Северная Голландия.
• Игорь Александр ; Ф. Кейт Ханна (1975). Теория автоматов: инженерный подход . Нью-Йорк: Крейн Руссак. ISBN 978-0-8448-0657-0.
• Марвин Мински (1967). Вычисления: Конечные и бесконечные машины . Принстон, Нью-Джерси: Прентис Холл.
• Джон К. Мартин (2011). Введение в языки и теорию вычислений . Нью-Йорк: МакГроу Хилл. ISBN 978-0-07-319146-1.

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

• dk.brics.automaton
• Либфа