Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.
Содержание
Терминология
Символ — любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ — это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.
- Слово — строка символов, создаваемая через конкатенацию (соединение).
- Алфавит — конечный набор различных символов (множество символов)
- Язык — множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.
- Автоматы
Автоматы могут быть детерминированные и недетерминированные.
- Детерминированный Конечный Автомат (ДКА) — последовательность (кортеж) из пяти элементов (Q,Σ,δ,S0,F){displaystyle (Q,Sigma ,delta ,S_{0},F)} , где:
- Q{displaystyle Q} — множество состояний автомата
- Σ{displaystyle Sigma } — алфавит языка, который понимает автомат
- δ{displaystyle delta } — функция перехода, такая что δ:Q×Σ→Q{displaystyle delta :Qtimes Sigma rightarrow Q}
- S0∈Q{displaystyle S_{0}in Q} — начальное состояние
- F⊆Q{displaystyle Fsubseteq Q} — множество конечных состояний.
, где:
— множество состояний автомата
— алфавит языка, который понимает автомат
— функция перехода, такая что δ:Q×Σ→Q{displaystyle delta :Qtimes Sigma rightarrow Q}
— начальное состояние
— множество конечных состояний.- Недетерминированный Конечный Автомат (НКА) — последовательность (кортеж) из пяти элементов (Q,Σ,Δ,S,F){displaystyle (Q,Sigma ,Delta ,S,F)} , где:
- Q{displaystyle Q} — множество состояний автомата
- Σ{displaystyle Sigma } — алфавит языка, который понимает автомат
- Δ{displaystyle Delta } — отношение перехода, Δ={<q,a,p>:q,p∈Q,a∈Σ∩{e}}{displaystyle Delta ={<q,a,p>:q,pin Q,ain Sigma cap {e}}} , где {e}{displaystyle {e}} — пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)
- S⊆Q{displaystyle Ssubseteq Q} — множество начальных состояний
- F⊆Q{displaystyle Fsubseteq Q} — множество конечных состояний.
, где:
— отношение перехода, Δ={<q,a,p>:q,p∈Q,a∈Σ∩{e}}{displaystyle Delta ={<q,a,p>:q,pin Q,ain Sigma cap {e}}}
, где {e}{displaystyle {e}}
— пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)
— множество начальных состояний- Слово
- Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом.Набор всех слов записывается как Σ*.
- Принимаемое слово
- Слово w ∈ Σ* принимается автоматом, если qn ∈ F.
Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита Σ{displaystyle Sigma }
таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:L={w∈Σ⋆|δ^(S0,w)∈F}{displaystyle L={win Sigma ^{star }|{hat {delta }}(S_{0},w)in F}}
Обычно автомат переходит из состояния в состояние с помощью функции перехода δ{displaystyle delta }
, читая при этом один символ из ввода. Есть автоматы, которые могут перейти в новое состояние без чтения символа. Функция перехода без чтения символа называется ϵ{displaystyle epsilon } -переход (эпсилон-переход).
-переход (эпсилон-переход).Применение
Теория автоматов лежит в основе всех цифровых технологий и программного обеспечения, так например компьютер является частным случаем практической реализации конечного автомата.
Часть математического аппарата теории автоматов напрямую применяется при разработке лексеров и парсеров для формальных языков, в том числе языков программирования, а также при построении компиляторов и разработке самих языков программирования.
Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.
Типовые задачи
- Построение и минимизация автоматов — построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
- Синтез автоматов — построение системы из заданных «элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется структурным. Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.
См. также
- Лемма о накачке
- Абстрактный автомат
- Игра «Жизнь»
- Минимальная форма автомата
- Теорема Шеннона — Лупанова
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: Вильямс, 2002. — С. 528. — ISBN 0-201-44124-1.
- Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. — C. 112.
