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


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

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

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

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

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

Automata

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

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

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

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

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

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

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

Автомат

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

Детерминированный конечный автомат представлен формально с помощью 5-кортежа <Q, Е , б , д 0 , F> , где:
  • Q представляет собой конечное множество состояний .
  • Σ является конечным множеством символов , называемый алфавитом автомата.
  • δ представляет собой переходную функцию , то есть, δ: Q × Σ → Q.
  • д 0 это начальное состояние , то есть состояние автомата перед любым входом было обработано, где д 0 ∈ Q.
  • F представляет собой множество состояний Q (т.е. F⊆Q) называется принимать состояния .
Введите слово
Автомат читает конечную строку из символов а 1 , A 2 , ...., А п , где I  ∈ E, которая называется входным словом . Множество всех слов обозначается Е *.
Бежать
Последовательность состояний д 0 , Q 1 , д 2 , ...., д п , где д я  ∈ Q такие , что д 0 является начальное состояние и д I  = δ (д я-1 , А я ) для 0 <г ^ п, является запуск автомата на входном слове ш = а 1 , A 2 , ...., А п  ∈ Σ *. Другими слова, сначала автомат находится в начальном состоянии Q 0 , а затем автомат считывает символы входного слова в последовательности. Когда автомат считывает символ а я прыгает утверждать Q I  = б (д я-1 , А я ). д п называется быть конечным состоянием в перспективе.
Принимая слово
Слово W ∈ Е * принимается автоматом , если д п  ∈ F.
Признанный язык
Автомат может распознавать формальный язык . Язык L ⊆ Σ * распознаваться автомата является множество всех слов, которые принимаются автоматом.
распознаваемых языков
В узнаваемых языках являются множеством языков, которые распознаются некоторым автоматом. Для приведенного выше определения автоматов узнаваемых языков являются регулярными языками . Для различных определений автоматов, узнаваемые языки разные.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(такая же мощность)      (такая же мощность) недетерминированный конечный автомат (НКА) (выше слабее)       (ниже сильнее) Детерминированная Push Down Automaton (DPDA-I) с 1 нажатием вниз магазином Недетерминированного Push Down Automaton (NPDA-I) с 1 толкать вниз магазин Linear Bounded Automaton (LBA) Детерминированные Push Down автоматного (DPDA-II) с 2 толчком вниз магазинами недетерминированного Push Down автоматных (NPDA-II) с 2 толчком вниз магазинами Детерминированного Тьюринга машин (DTM) Недетерминированные машинами Тьюринга ( НТМ) Вероятностный машин Тьюринга (PTM) Многоленточная машина Тьюринга (MTM) многомерная машина Тьюринг
























Приложения

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

Автоматные имитаторы

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

Подключение к теории категорий

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

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

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

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

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

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

внешняя ссылка