Языки и автоматы

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

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

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

Детерминированный конечный автомат (ДКА) — последовательность (кортеж) из пяти элементов (Q , Σ , δ , S0, F), где:

Недетерминированный конечный автомат (НКА) — последовательность (кортеж) из пяти элементов (Q , Σ , ∆, S, F), где:
Q — множество состояний автомата
Σ — алфавит языка, который понимает автомат
∆ — отношение перехода
S С Q — множество начальных состояний
F C Q — множество конечных состояний.

СЛОВО
Автомат читает конечную строку символов a1,a2,…., an , где ai ∈ Σ, которая называется входным словом. Набор всех слов записывается как Σ*.

ПРИНИМАЕМОЕ СЛОВО

ПРИМЕНЕНИЕ
Теория автоматов лежит в основе всех цифровых технологий и программного обеспечения, так например компьютер является частным случаем практической реализации конечного автомата.
Часть математического аппарата теории автоматов напрямую применяется при разработке лексеров и парсеров для формальных языков, в том числе языков программирования, а также при построении компиляторов и разработке самих языков программирования.
Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.