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

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

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

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

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

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

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

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

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

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

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

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

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

Автоматы могут быть детерминированные и недетерминированные.

Детерминированный конечный автомат (ДКА) — последовательность (кортеж) из пяти элементов ${\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 }$-переход (эпсилон-переход).

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

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

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

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

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

• Применение теории автоматов