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

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

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

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

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

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

Автомат

Автомат — последовательность (кортеж) из пяти элементов $(Q, \Sigma, \delta, S_0, F)$, где:

• $Q$ — множество состояний автомата
• $\Sigma$ — алфавит языка, который понимает автомат
• $\delta$ — функция перехода, такая что $\delta : Q \times \Sigma \rightarrow Q$
• $S_0$ — начальное состояние
• $F$ — множество состояний, называемых «принимающие состояния».

Слово

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

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

Слово w ∈ Σ* принимается автоматом, если q_n ∈ F.

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

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

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

Применение

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

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

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

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

См. также

• Лемма о накачке
• Абстрактный автомат
• Игра «Жизнь»
• Минимальная форма автомата

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: Вильямс, 2002. — С. 528. — ISBN 0-201-44124-1
• Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. — C. 112.

Ссылки

• Лекции по теории автоматов
• Теория Автоматов
• Применение теории автоматов