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

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

Классы автоматов (При нажатии на каждый слой открывается статья на эту тему) Изучение математических свойств таких автоматов - теория автоматов. Изображение представляет собой визуализацию автомата, распознающего строки, содержащие четное количество нулей. Автомат запускается в состоянии S1 и переходит в состояние отсутствия приема S2 после считывания символа 0. Чтение еще одного 0 заставляет автомат перейти обратно в состояние приема S1. В обоих состояниях символ 1 игнорируется при переходе в текущее состояние.

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

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

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

Автоматы играют важную роль в теории вычислений, построении компиляторов, искусственном интеллекте, синтаксическом анализе и формальная проверка.

Содержание

• 1 Автоматы
  • 1.1 Очень информативное описание
  • 1.2 Неформальное описание
  • 1.3 Формальное определение
    • 1.3.1 Определение конечных автоматов
• 2 Варианты определения автоматов
• 3 Классы автоматов
  • 3.1 Дискретные, непрерывные и гибридные автоматы
• 4 Иерархия по мощностям
• 5 Приложения
• 6 Симуляторы автоматов
• 7 Связь с теорией категорий
• 8 История
• 9 См. Также
• 10 Ссылки
• 11 Дополнительная литература
• 12 Внешние ссылки

Автоматы

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

Очень неформальное описание

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

Неформальное описание

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

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

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

Автомат

определение конечных автоматов

Детерминированный конечный автомат формально представлен 5-кратным набором Σ, δ,q0,F>, где:

• Q - конечный набор состояний.
• Σ - конечный набор символов, называемый алфавитом автомата.
• δ - переход функция, то есть δ: Q × Σ → Q.
• q0- это начальное состояние, то есть состояние автомата до обработки любого ввода, где q 0 ∈ Q.
• F - это набор состояний Q (т.е. F⊆Q), называемый состояниями принятия .

Входное слово

Автомат считывает конечную строку символов a 1,a2,...., a n, где a i ∈ Σ, которое называется входным словом. Набор всех слов обозначается Σ *.

Run

Последовательность состояний q 0,q1,q2,...., q n, где q i ∈ Q, такое что q 0 - начальное состояние и q i = δ (q i-1,ai) для 0 < i ≤ n, is a run of the automaton on an input word w = a1,a2,...., a n ∈ Σ *. Другими словами, сначала автомат находится в начальном состоянии q 0, а затем автомат последовательно считывает символы входного слова. Когда автомат считывает символ a i, он переходит в состояние q i = δ (q i-1,ai). q n называется конечным состоянием выполнения.

Принимающее слово

Слово w ∈ Σ * принимается автоматом, если q n ∈ F.

Распознаваемый язык

Автомат может распознать формальный язык. Язык L ⊆ Σ *, распознаваемый автоматом, - это набор всех слов, которые принимает автомат.

Распознаваемые языки

распознаваемые языки - это набор языков, которые распознаются каким-то автоматом. Для приведенного выше определения автоматов распознаваемыми языками являются обычные языки. Для разных определений автоматов распознаваемые языки различаются.

Определения вариантов автоматов

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

Входные данные

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

Состояния

• Конечные состояния: автомат, который содержит только конечное число состояний. Приведенное выше вводное определение описывает автомат с конечным числом состояний.
• Бесконечные состояния: автомат, который может не иметь конечного числа состояний или даже счетного числа состояний. Например, квантовый конечный автомат или топологический автомат имеет бесчисленное множество состояний.
• Стековая память: автомат может также содержать некоторые дополнительные память в виде стека , в который можно вставлять и выталкивать символы. Этот вид автоматов называется автоматом выталкивания

Переходная функция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автомат

Детерминированный конечный автомат (DFA) - наименьшая мощность. (такая же мощность) $|\; |\; \{\backslash \; displaystyle\; ||\}$(та же степень). Недетерминированный конечный автомат (NFA). (вверху слабее) $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$(ниже более сильный). Детерминированный автомат выталкивания вниз (DPDA-I). с 1 магазином опускания вниз. $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$. (NPDA-I). с 1 расширяемым магазином. $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$. Линейный ограниченный автомат (LBA). $\cap \; \{\; \backslash \; displaystyle\; \backslash \; cap\}$. Детерминированный автомат выталкивания вниз (DPDA-II). с 2 сохраняющими нажатиями вниз. $|\; |\; \{\backslash \; displaystyle\; ||\}$. (NPDA-II). с 2 открывающимися магазинами. $|\; |\; \{\backslash \; displaystyle\; ||\}$. Детерминированная машина Тьюринга (DTM). $|\; |\; \{\backslash \; displaystyle\; ||\}$. Недетерминированная машина Тьюринга (NTM). $|\; |\; \{\backslash \; displaystyle\; ||\}$. Вероятностная машина Тьюринга (PTM). $|\; |\; \{\backslash \; displaystyle\; ||\}$. Многоленточная машина Тьюринга (MTM). $|\; |\; \{\backslash \; displaystyle\; ||\}$. Многомерная машина Тьюринга

Приложения

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

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

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

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

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

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

Можно также определить автомат с переменными в смысле Норберта Винера в его книге Использование человека людьми через эндоморфизмы $от\; A\; i\; \to \; A\; i\; \{\backslash \; displaystyle\; A\_\; \{i\}\; \backslash \; к\; A\_\; \{i\}\}$. Затем можно показать, что такие гомоморфизмы переменных автоматов образуют математическую группу. В случае недетерминированных или других сложных видов автоматов последний набор эндоморфизмов может, однако, стать автоматом переменных группоидом. Следовательно, в самом общем случае категории автоматов с переменными любого вида - это или. Более того, категория обратимых автоматов тогда является 2-категорией, а также подкатегорией 2-категории группоидов или категорией группоидов.

История

Теория автоматов была разработана в середине 20 века в связи с конечными автоматами.

См. Также

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

Ссылки

Дополнительная литература

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

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

• Visual Automata Simulator, инструмент для моделирование, визуализация и преобразование конечных автоматов и машин Тьюринга, Жан Бове
• JFLAP
• dk.brics.automaton
• libfa