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

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

Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.

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

Терминология

Символ — любой атомарный (то есть неделимый более без потери смысла) блок данных, который может производить эффект на машину. Чаще всего символ — это буква некоего формального языка. Например, символы, применяемые во многих языках программирования, включают буквы обычного языка, разделители, также какие-то дополнительные знаки. Но символом может быть, к примеру, ключевое слово целиком некоего языка программирования (if, for, while и т. д.), графический элемент диаграммы и т. д.

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

Назначение формальных автоматов

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

Порядок работы автомата

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

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

Начало и завершение работы автомата

Начало работы автомата полностью задаётся его «начальной конфигурацией», включающей разбираемое слово и состояние, в котором находится автомат. Если автомат находится в одном из начальных состояний и имеется функция перехода для данного состояния и первого символа читаемой цепочки, автомат совершает соответствующий переход, сдвигает читающую головку на входном слове и (в простейшем случае — конечные автоматы) переходит к исследованию следующего символа входа.

Для приёма (или, как говорят, допуска) входного слова автоматом необходимо выполнение двух условий:

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

Под «пустым переходом» или «переходом по пустому символу» здесь понимается переход из одного состояния в другое, когда очередной символ из входного слова не считывается или, иначе говоря, «читается» пустой символ. Обозначения см. ниже.

Заметим, что автомат должен принять все допустимые слова описываемого им языка и при этом не принять ни одного слова, которое в этот язык не входит.

Если входное слово не принадлежит языку, то автомат либо

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

Основные виды автоматов

По сложности разбираемых языков

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

По классификации Н. Хомского, известны четыре основных вида (по разнообразию, по сложности) формальных языков:

1. (Регулярные)
3. (Контекстно-зависимые)
4. Языки общего вида (без доп. ограничений)

Для разбора слов из регулярных языков подходят формальные автоматы самого простого устройства, т. н. (конечные автоматы). Их функция перехода задаёт только смену состояний и, возможно, сдвиг (чтение) входного символа.

Для разбора слова из контекстно-свободных языков в автомат приходится добавлять «магазинную ленту» или «стек», в который при каждом переходе записывается цепочка на основе соответствующего алфавита магазина. Такие автоматы называют «(магазинные автоматы)».

Для контекстно-зависимых языков разработаны ещё более сложные , а для языков общего вида — машина Тьюринга.

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

Заметим, что многие задачи поиска сведений во всемирной сети Интернет записываются в понятиях регулярных языков (т.е. с самыми жёсткими ограничениями), а большинство применяемых универсальных языков программирования вполне успешно воплощены на основе контекстно-свободных грамматик (хотя и с некоторыми усовершенствованиями, см. "атрибутные грамматики"). К числу немногих и очень своеобразных исключений относится язык программирования (ЛИСП) (LISP), разработанный на основе контекстно-зависимых языков. А Машина Тьюринга, при всей своей (в теории) универсальности и мощи, оказывается настолько сложной и неудобной для использования в приложениях, что используется только для теоретического анализа.

По однозначности функции переходов

Для одной и той же текущей конфигурации (состояние автомата, читаемый входной символ и, возможно, некоторые дополнительные параметры для сложных видов автоматов, например, содержание стека в магазинном автомате) функции переходов формального автомата могут задавать как единственный (определённый, детерминированный) переход, так и несколько разных. Иначе говоря, для одной и той же конфигурации автомата вообще говоря возможно существование нескольких функций переходов.

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

По данному признаку автоматы также делятся на детерминированные (определённые) и недетерминированные. Важность данного разделения объясняется ещё и тем, как свойство детерминированности влияет на толкование допуска слова автоматом.

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

Понятно, что отслеживание и учёт возможных возвратов при разборе слова заметно усложняет работу программиста. Поэтому возникает вопрос, можно ли так преобразовать автомат, чтобы он из недетерминированного стал детерминированным и, в целом ряде случаев, поэтому более удобным для работы с ним. В теории автоматов доказано, что для регулярных языков и соответствующих им конечных автоматов это можно сделать всегда. А для остальных видов языков (по Н. Хомскому), начиная с контекстно-свободных и соответствующих им автоматов, в общем случае — уже нет.

С другой стороны отмечается, что недетерминированные автоматы обычно имеют заметно меньший объём, их логика работы легче понимается человеком. Заметим, что при использовании многопроцессорных (многоядерных) вычислительных машин сама возможность распараллеливания нередко тесно связана с недетерминированностью алгоритма. Программа, все части которой должны выполняться в строго определённой последовательности, распараллеливанию не поддаётся….

Примеры формального определения для конечных автоматов

Автоматы могут быть .

(Детерминированный) (конечный автомат) (ДКА) — последовательность (кортеж) из пяти элементов ${\displaystyle (Q,\Sigma ,\delta ,S_{0},F)}$, где:

• ${\displaystyle Q}$ — множество состояний автомата
• ${\displaystyle \Sigma }$ — алфавит языка, который понимает автомат
• ${\displaystyle \delta }$ — функция перехода, такая что ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$
• ${\displaystyle S_{0}\in Q}$ — начальное состояние
• ${\displaystyle F\subseteq Q}$ — множество конечных состояний.

(Недетерминированный конечный автомат) (НКА) — последовательность (кортеж) из пяти элементов ${\displaystyle (Q,\Sigma ,\Delta ,S,F)}$, где:

• ${\displaystyle Q}$ — множество состояний автомата
• ${\displaystyle \Sigma }$ — алфавит языка, который понимает автомат
• ${\displaystyle \Delta }$ — отношение перехода, ${\displaystyle \Delta =\{<q,a,p>:q,p\in Q,a\in \Sigma \cup \{e\}\}}$, где ${\displaystyle \{e\}}$ — пустое слово. То есть, НКА может совершить переход из состояния q в состояние p, в отличие от ДКА, через пустое слово (то есть не читая очередной символ со входа), а также перейти из q по a в одно из нескольких состояний (в ДКА возможен переход из q по a не более чем в одно состояние из Q, отсюда определённость (или, по-английски, детерминированность) всех переходов такого автомата и его название).
• ${\displaystyle S\subseteq Q}$ — множество начальных состояний
• ${\displaystyle F\subseteq Q}$ — множество конечных состояний.

Слово

Автомат читает конечную строку символов a₁, a₂, …., a_n , где a_i ${\displaystyle \in }$ Σ, которая называется входным словом. Набор всех слов записывается как Σ*.

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

Слово w ${\displaystyle \in }$ Σ* принимается автоматом, если q_n ${\displaystyle \in }$ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита ${\displaystyle \Sigma }$ таких, что если эти слова вводятся в M, по окончании обработки он приходит в одно из принимающих состояний F:

${\displaystyle L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(S_{0},w)\in F\}}$

Обычно автомат переходит из состояния в состояние с помощью функции перехода ${\displaystyle \delta }$, читая при этом один символ из ввода. Есть автоматы, которые могут перейти в новое состояние без чтения символа. Функция перехода без чтения символа называется ${\displaystyle \epsilon }$-переход (эпсилон-переход).

Применение

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

Часть математического аппарата теории автоматов напрямую применяется при разработке (лексических) и синтаксических анализаторов для формальных языков, в том числе языков программирования, а также при построении компиляторов и разработке самих языков программирования, (описания аппаратуры), а также разметки.

Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и (сложности) задач.

Типовые задачи

• Построение и минимизация автоматов — построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
• Синтез автоматов — построение системы из заданных «элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется . Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.

См. также

• (Лемма о накачке)
• (Абстрактный автомат)
• Клеточный автомат
• Игра «Жизнь»
• (Минимальная форма автомата)
• (Теорема Шеннона — Лупанова)
• (Муравей Лэнгтона)

Примечания

1. Современная теория автоматов, 2013, с. 5.
2. (Серебряков В. А.), Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования от 3 января 2022 на Wayback Machine — М.: МЗ-Пресс, 2006 г., 2-е изд. —

Литература

• (Виктор Михайлович Глушков). Синтез цифровых автоматов. — М.: Государственное издательство физико-математической литературы, 1962. — С. 476.

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: Вильямс, 2002. — С. 528. — .
• (Серебряков В. А.), Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 2006 г., 2-е изд. —
• (Касьянов В. Н.) Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. — C. 112.
• Современная теория автоматов. Калининград: Изд-во БФУ им. И. Канта, 2013. 261 с.: ил. .

Ссылки