Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Автоматы [ править ]

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

Очень неформальное описание [ править ]

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

Неофициальное описание [ править ]

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

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

Формальное определение [ править ]

Автомат

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

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

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

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

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

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

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

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

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

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

Классы автоматов [ править ]

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

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

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

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

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

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

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

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




















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



Приложения [ править ]

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

Симуляторы автоматов [ править ]

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

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

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

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

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

История [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. Перейти ↑ Yan, Song Y. (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 , doi : 10.1093 / qmath / hay015 , S2CID 3962424 
  3. ^ Chakraborty, P .; Saxena, PC; Катти, КП (2011). «Пятьдесят лет моделирования автоматов: обзор» . ACM Inroads . 2 (4): 59–70. DOI : 10.1145 / 2038876.2038893 . S2CID 6446749 . 
  4. ^ Иржи Adámek и Věra Trnkova . 1990. Автоматы и алгебры в категориях . Kluwer Academic Publishers: Дордрехт и Прага
  5. Перейти ↑ Mac Lane, Saunders (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. ^ Агилар, М. и Mahajan, S.2010. «Моноидальные функторы, виды и алгебры Хопфа» .
  10. ^ Meseguer, J., Montanari, U .: 1990 сети Петри являются моноидами. Информация и вычисления 88 : 105–155
  11. ^ Махони, Майкл С. "Структуры вычислений и математическая структура природы" . The Rutherford Journal . Проверено 7 июня 2020 .

Дальнейшее чтение [ править ]

  • Джон Э. Хопкрофт , Раджив Мотвани , Джеффри Д. Ульман (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). Автоматы, вычислимость и сложность: теория и приложения . Пирсон. ISBN 978-0-13-228806-4.
  • Саломаа, Арто (1985). Вычисления и автоматы . Энциклопедия математики и ее приложений. 25 . Издательство Кембриджского университета . ISBN 978-0-521-30245-6. Zbl  0565.68046 .
  • Андерсон, Джеймс А. (2006). Теория автоматов в современных приложениях . При участии Тома Хеда. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-61324-8. Zbl  1127.68049 .
  • Конвей, Дж. Х (1971). Регулярная алгебра и конечные машины . Математика Чепмена и Холла. Лондон: Чепмен и Холл . Zbl  0231.94041 .
  • Джон М. Хауи (1991) Автоматы и языки , Clarendon Press ISBN 0-19-853424-8 MR 1254435 
  • Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Издательство Кембриджского университета . ISBN 978-0-521-84425-3. Zbl  1188.68177 .
  • Джеймс П. Шмайзер , Дэвид Т. Барнард (1995). Создание порядка синтаксического анализа сверху вниз с синтаксическим анализом снизу вверх . Эльзевир Северная Голландия.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