Теория автоматов - Automata theory

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

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

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

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

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

Автоматы

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

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

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

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

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

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

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

Автомат

значение конечные автоматы

Детерминированный конечный автомат представлен формально 5-кратный Σ, δ, q0, F>, где:
  • Q - конечный набор состояния.
  • Σ конечный набор символы, называется алфавит автомата.
  • δ это функция перехода, то есть δ: Q × Σ → Q.
  • q0 это начальное состояние, то есть состояние автомата до обработки любого ввода, где q0∈ Q.
  • F - это набор состояний Q (то есть F⊆Q), называемый принять состояния.
Входное слово
Автомат читает конечное строка символов а1, а2, ...., ап , гдея ∈ Σ, который называется входное слово. Множество всех слов обозначается Σ *.
Бегать
Последовательность состояний q0, q1, q2, ...., qп, где qя ∈ Q такой, что q0 - начальное состояние, а qя = δ (qя-1, ая) для 0 бегать автомата на входном слове w = a1, а2, ...., ап ∈ Σ *. Другими словами, сначала автомат находится в стартовом состоянии q0, а затем автомат последовательно считывает символы входного слова. Когда автомат читает символ aя он переходит в состояние qя = δ (qя-1, ая). qп считается конечное состояние пробега.
Принятие слова
Слово w ∈ Σ * принимается автоматом, если qп ∈ F.
Признанный язык
Автомат может распознать формальный язык. Распознаваемый автоматом язык L ⊆ Σ * - это набор всех слов, которые принимает автомат.
Узнаваемые языки
В узнаваемые языки - это набор языков, распознаваемых каким-либо автоматом. Для приведенного выше определения автоматов распознаваемыми языками являются обычные языки. Для разных определений автоматов распознаваемые языки разные.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автомат
Детерминированный конечный автомат (DFA) - Самая низкая мощность

(та же мощность) (та же мощность)
Недетерминированный конечный автомат (NFA)
(вверху слабее) (ниже сильнее)
Детерминированный автомат выталкивания вниз (DPDA-I)
с 1 магазином push-down

Недетерминированный автомат выталкивания вниз (NPDA-I)
с 1 магазином push-down

Линейно ограниченный автомат (LBA)

Детерминированный автомат выталкивания вниз (DPDA-II)
с 2 магазином push-down

Недетерминированный автомат выталкивания вниз (NPDA-II)
с 2 магазинами push-down

Детерминированная машина Тьюринга (DTM)

Недетерминированная машина Тьюринга (NTM)

Вероятностная машина Тьюринга (PTM)

Многолента машина Тьюринга (MTM)

Многомерная машина Тьюринга

Приложения

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

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

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

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

Можно выделить несколько различных категории автоматов[4] следуя классификации автоматов на разные типы, описанной в предыдущем разделе. Математическая категория детерминированных автоматов, последовательные машины или последовательные автоматы, а машина Тьюринга с гомоморфизмами автоматов, определяющими стрелки между автоматами, является Декартова закрытая категория,[5][6] он имеет как категориальные пределы, так и копределы. Гомоморфизм автоматов отображает пятерку автомата Ая на пятерку другого автомата Аj.[7] Гомоморфизмы автоматов также можно рассматривать как автоматные преобразования или как гомоморфизмы полугрупп, когда пространство состояний S, автомата определяется как полугруппа Sг. Моноиды также считаются подходящей настройкой для автоматов в моноидальные категории.[8][9][10]

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

Можно также определить переменный автомат, в том смысле Норберт Винер в его книге о Использование человеком человеческих существ через эндоморфизмы . Затем можно показать, что такие гомоморфизмы переменных автоматов образуют математическую группу. Однако в случае недетерминированных или других сложных видов автоматов последний набор эндоморфизмов может стать переменный автомат группоид. Следовательно, в самом общем случае категории автоматов с переменными любого вида категории группоидов или группоидные категории. Более того, тогда категория обратимых автоматов является 2 категории, а также подкатегория 2-категории группоидов, или категория группоидов.

История

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

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

использованная литература

  1. ^ Ян, Сонг Ю. (1998). Введение в формальные языки и машинные вычисления. Сингапур: World Scientific Publishing Co. Pte. Ltd. С. 155–156. ISBN  9789810234225.
  2. ^ Ferraguti, A .; Micheli, G .; Шнайдер, Р. (2018), Неприводимые композиции полиномов второй степени над конечными полями имеют регулярную структуру, Ежеквартальный журнал математики, 69, Oxford University Press, стр. 1089–1099, arXiv:1701.06040, Дои:10.1093 / qmath / hay015, S2CID  3962424
  3. ^ Чакраборти, П .; Saxena, P.C .; Катти, К. П. (2011). «Пятьдесят лет моделирования автоматов: обзор». ACM Inroads. 2 (4): 59–70. Дои:10.1145/2038876.2038893. S2CID  6446749.
  4. ^ Иржи Адамек и Вера Трнкова. 1990. Автоматы и алгебры в категориях. Kluwer Academic Publishers: Дордрехт и Прага
  5. ^ Мак-Лейн, Сондерс (1971). Категории для рабочего математика. Нью-Йорк: Спрингер. ISBN  9780387900360.
  6. ^ Декартова закрытая категория В архиве 16 ноября 2011 г. Wayback Machine
  7. ^ Категория автоматов В архиве 15 сентября 2011 г. Wayback Machine
  8. ^ http://www.math.cornell.edu/~worthing/asl2010.pdf Джеймс Уортингтон, 2010 г. Детерминирование, забвение и автоматы в моноидальных категориях. Ежегодное собрание ASL в Северной Америке, 17 марта 2010 г.
  9. ^ Агиар, М., Махаджан, С. 2010. «Моноидальные функторы, виды и алгебры Хопфа».
  10. ^ Месегер Дж., Монтанари У.: Сети Петри, 1990 г., являются моноидами. Информация и вычисления 88:105–155
  11. ^ Махони, Майкл С. «Структуры вычислений и математическая структура природы». Журнал Резерфорда. Получено 2020-06-07.

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

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