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

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

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

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

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

История

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

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

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

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

Автоматы

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

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

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

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

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

Автомат

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

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

Если $Q$ конечно, то $M$ является конечным автоматом .

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

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

Бегать

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

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

Акцептор

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

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

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

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

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

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

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

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

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

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

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

Вход

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

состояния

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

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

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

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

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

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

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

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

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

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

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

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

Автомат	Узнаваемые языки
Недетерминированный/детерминированный конечный автомат (FSM)	обычные языки
Детерминированный автомат с понижением уровня (DPDA)	детерминированные контекстно-свободные языки
Нажимной автомат (КПК)	контекстно-свободные языки
Линейный ограниченный автомат (LBA)	контекстно-зависимые языки
Машина Тьюринга	рекурсивно перечислимые языки
Детерминированный автомат Бюхи	ω-предельные языки
Недетерминированный автомат Бюхи	ω-регулярные языки
Автомат Рабина , автомат Стритта , автомат четности , автомат Мюллера
Взвешенный автомат

и гибридные

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

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

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

Автомат

Детерминированный конечный автомат (DFA) — наименьшая степень (та же мощность) $||$ (та же мощность) Недетерминированный конечный автомат (NFA) (выше слабее) $\cap$ (ниже сильнее) Детерминированный автомат с нажатием вниз (DPDA-I) с 1 выдвижным магазином $\cap$ Недетерминированный автомат с нажатием вниз (NPDA-I) с 1 выдвижным магазином $\cap$ Линейный ограниченный автомат (LBA) $\cap$ Детерминированный автомат с нажатием вниз (DPDA-II) с 2 выдвижными магазинами $||$ Недетерминированный автомат с нажатием вниз (NPDA-II) с 2 выдвижными магазинами $||$ Детерминированная машина Тьюринга (DTM) $||$ Недетерминированная машина Тьюринга (НТМ) $||$ Вероятностная машина Тьюринга (ПТМ) $||$ Многоленточная машина Тьюринга (МТМ) $||$ Многомерная машина Тьюринга

Приложения

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

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

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

Теоретико-категорные модели

Можно определить несколько различных категорий автоматов. следуя классификации автоматов на разные типы, описанной в предыдущем разделе. Математическая категория детерминированных автоматов, последовательных машин или последовательных автоматов и машин Тьюринга с гомоморфизмами автоматов , определяющими стрелки между автоматами, является декартовой замкнутой категорией , он имеет как категориальные пределы , так и копределы . Гомоморфизм автоматов отображает пятерку автомата A _i на пятерку другого автомата А _Дж . Гомоморфизмы автоматов также можно рассматривать как преобразования автоматов или как гомоморфизмы полугрупп , когда пространство состояний S автомата определяется как полугруппа S _g . Моноиды также считаются подходящей средой для автоматов в моноидальных категориях .

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

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

См. также

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

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

• Джон Э. Хопкрофт ; Раджив Мотвани ; Джеффри Д. Уллман (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) Автоматы и языки , Clarendon Press ISBN   0-19-853424-8 МР 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
• либфа