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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Терминология[править | править исходный текст]

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

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


Автоматы

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

Детерминированный Конечный Автомат (ДКА) — последовательность (кортеж) из пяти элементов (Q, \Sigma, \delta, S_0, F), где:
  • Q — множество состояний автомата
  • \Sigma — алфавит языка, который понимает автомат
  • \delta — функция перехода, такая что \delta : Q \times \Sigma \rightarrow Q
  • S_0 \in Q  — начальное состояние
  • F \subseteq Q  — множество конечных состояний.
Недетерминированный Конечный Автомат (НКА) — последовательность (кортеж) из пяти элементов (Q, \Sigma, \Delta, S_0, F), где:
  • Q — множество состояний автомата
  • \Sigma — алфавит языка, который понимает автомат
  • \Delta — отношение перехода, \Delta=\{<q,a,p>: q,p \in Q, a \in  \Sigma \cap \{e\}\}, где \{e\} - пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)
  • S_0 \in Q  — начальное состояние
  • F \subseteq Q  — множество конечных состояний.
Слово
Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом.Набор всех слов записывается как Σ*.
Принимаемое слово
Слово w ∈ Σ* принимается автоматом, если qn ∈ 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.

Ссылки[править | править исходный текст]