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

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

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

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

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

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

История

Теория абстрактных автоматов была разработана в середине 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 ^{*}}$

Бегать

Последовательность состояний , где такой, что для , представляет собой запуск автомата на входе , начинающийся с состояния . Другими словами, сначала автомат находится в начальном состоянии и получает вход . Для и каждого следующего во входной строке автомат выбирает следующее состояние в соответствии с функцией перехода , пока не будет прочитан последний символ , оставляя машину в конечном состоянии запуска, . Аналогично, на каждом шаге автомат выдает выходной символ в соответствии с выходной функцией . ${\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]
• Конечные состояния : автомат, содержащий только конечное число состояний.
• Бесконечные состояния : Автомат, который может не иметь конечного числа состояний или даже счетного числа состояний. Различные виды абстрактной памяти могут использоваться для предоставления таким машинам конечных описаний.
• Память стека : Автомат может также содержать некоторую дополнительную память в виде стека , в котором символы могут быть вставлены и вытащены. Этот тип автомата называется автоматом pushdown .
• Память очереди : Автомат может иметь память в форме очереди . Такая машина называется машиной очереди и является полной по Тьюрингу.
• Ленточная память : Входы и выходы автоматов часто описываются как входные и выходные ленты . Некоторые машины имеют дополнительные рабочие ленты , включая машину Тьюринга , линейный ограниченный автомат и логарифмический преобразователь .

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

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

Условие принятия

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

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

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

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

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

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

Типы автоматов

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

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

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

Иерархия полномочий

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

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

• Джон Э. Хопкрофт ; Раджив Мотвани ; Джеффри Д. Ульман (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Pearson Education. ISBN 978-0-201-44124-6.
• Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. 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. Cambridge University Press . ISBN 978-0-521-30245-6. Збл  0565.68046.
• Андерсон, Джеймс А. (2006). Теория автоматов с современными приложениями . С участием Тома Хэда. Кембридж: Cambridge University Press . ISBN 978-0-521-61324-8. Збл  1127.68049.
• Conway, JH (1971). Регулярная алгебра и конечные машины . Серия Chapman and Hall Mathematics. Лондон: Chapman & Hall . Zbl  0231.94041.
• Джон М. Хауи (1991) Автоматы и языки , Clarendon Press ISBN 0-19-853424-8 MR 1254435 
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Cambridge University Press . ISBN 978-0-521-84425-3. Збл  1188.68177.
• Джеймс П. Шмейсер; Дэвид Т. Барнард (1995). Создание порядка разбора сверху вниз с помощью разбора снизу вверх . Elsevier North-Holland.
• Игорь Александр ; Ф. Кит Ханна (1975). Теория автоматов: инженерный подход . Нью-Йорк: Крейн Руссак. ISBN 978-0-8448-0657-0.
• Марвин Мински (1967). Вычисления: Конечные и бесконечные машины . Принстон, Нью-Джерси: Prentice Hall.
• Джон К. Мартин (2011). Введение в языки и теория вычислений . Нью-Йорк: McGraw Hill. ISBN 978-0-07-319146-1.

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

• dk.brics.автомат
• либфа