WikiSort.ru - Не сортированное

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

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

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

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

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

Автоматы

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

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

Слово

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

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

Слово w ∈ Σ* принимается автоматом, если q_n ∈ 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 }$ -переход (эпсилон-переход).

Применение

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

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

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

См. также

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

Литература

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

Ссылки

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