Шпаргалки / Математика / Школа / Дискретная математика

Конечные автоматы

Что такое конечный автомат

Конечный автомат (КА) — это математическая модель, которая описывает систему с ограниченным числом состояний, переходящих друг в друга в ответ на входные символы.

Автомат — это механизм, который в зависимости от входа (символов) меняет своё состояние и решает, принимать ли строку или нет.

Где применяются

Конечные автоматы — это способ формально описывать поведение систем, которые могут находиться только в ограниченном числе состояний и переходить между ними в зависимости от входных данных.
Главное свойство автомата — память ограничена: он не может запомнить всё, что было, а только “состояние”, которое кратко отражает прошлое.

1. Лексический анализ в компиляторах

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

Пример:
В строке “while count < 10” нужно выделить:

while — ключевое слово
count — идентификатор
< — оператор
10 — число

Каждый из этих шаблонов описывается регулярным выражением, а регулярные выражения реализуются через конечные автоматы.
Например, автомат для числа может быть таким:

принимает цифры 0–9
допускает точку .
допускает экспоненту e или E

На практике это делает лексический анализатор (lexer), построенный на основе автомата.

2. Регулярные выражения и поиск по тексту

Каждое регулярное выражение можно превратить в конечный автомат.
Это делает поиск по шаблону быстрым и формальным.

Пример:
Регулярка a(b|c)*d соответствует всем строкам, которые начинаются на a, оканчиваются на d и между ними — любое количество b или c.
Автомат проходит по символам и в конце проверяет, оказался ли он в принимающем состоянии.

Так работают поисковые механизмы в текстовых редакторах, IDE и утилитах вроде grep.

3. Проверка корректности ввода

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

Пример:
Валидация почты, номера телефона, пароля:

user@domain.com можно описать автоматом, который проверяет порядок символов:
буквы → @ → буквы → . → домен.
Пароль может проверяться автоматом, который требует хотя бы одну цифру, одну букву и один спецсимвол.

4. Управление состояниями в программах

Во многих программах поведение зависит от текущего состояния.

Пример:
Автоматизированный банкомат (ATM):

Idle → ждет карту
CardInserted → ждет PIN
Authenticated → выполняет операции
CardEjected → возвращается к Idle

Каждый переход происходит при определённом событии (вставка карты, ввод PIN, подтверждение и т. д.).

5. Протоколы связи и сетевые системы

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

Пример:
Упрощённая модель TCP:

CLOSED
SYN_SENT
SYN_RECEIVED
ESTABLISHED
FIN_WAIT
CLOSED (завершение соединения)

Каждое состояние — фаза соединения.
Переходы происходят при получении пакетов (SYN, ACK, FIN и т. д.).

6. Цифровые схемы и микроконтроллеры

Конечные автоматы применяются в цифровой логике и управляющих устройствах.
Многие электронные схемы работают как автоматы: они реагируют на входные сигналы и меняют своё состояние.

Пример:
Стиральная машина:

Ожидание запуска
Набор воды
Стирка
Полоскание
Отжим
Готово

Каждое действие активируется по сигналу датчика (вода набрана, время вышло и т. д.).

7. Искусственный интеллект и игровая логика

В играх поведение персонажей часто моделируется конечными автоматами.

Пример:
Персонаж может быть в одном из состояний:

Патрулирует
Замечает игрока
Преследует
Атакует
Отступает

Переходы происходят при определённых событиях (например, “видит игрока”, “получил урон”, “цель исчезла”).

8. Управление пользовательскими интерфейсами (UI)

UI-приложения тоже часто описываются как автоматы:
каждое окно, форма или экран — это состояние, а действия пользователя — переходы.

Пример:
Мобильное приложение:

Экран входа
Главное меню
Настройки
Профиль пользователя

Переходы — это нажатия кнопок, логин, выход и т. д.

9. Биоинформатика и распознавание последовательностей

Конечные автоматы используются для анализа последовательностей ДНК или белков, где важен порядок символов.

Пример:
Автомат может искать фрагмент нуклеотидной последовательности ATG как начало гена.

10. Обработка сигналов и управление роботами

В системах реального времени автоматы описывают реакцию на события датчиков.

Пример:
Робот с тремя состояниями:

Поиск цели
Наведение
Действие (захват)
Если цель потеряна — возвращается к Поиску.

Резюме

Конечные автоматы применяются везде, где система:

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

Они лежат в основе:

компиляторов,
текстовых анализаторов,
сетевых протоколов,
микроконтроллеров,
логики игр,
и даже некоторых систем искусственного интеллекта.

По сути, конечные автоматы — это универсальная модель поведения, которая описывает, что система делает при каждом возможном вводе в зависимости от своего текущего состояния.

Формальное определение

Детерминированный конечный автомат (ДКА) задаётся как 5-ка:

A = (Q, \Sigma, \delta, q_0, F)

где:

$$Q$$ — конечное множество состояний
$\Sigma$ — конечный алфавит (набор входных символов)
$\delta: Q \times \Sigma \to Q$ — функция переходов
$q_0 \in Q$ — начальное состояние
$F \subseteq Q$ — множество заключительных (допускающих) состояний

Как работает

Автомат начинает в состоянии $$q_0$$
Читает входное слово $w = a_1 a_2 \dots a_n$
Для каждого символа $$a_i$$ применяет переход:
$q_{i+1} = \delta(q_i, a_i)$
После чтения всей строки, если конечное состояние $q_n \in F$ , то автомат принимает строку, иначе отклоняет.

Пример ДКА

Пусть алфавит $\Sigma = \{0,1\}$ .

Нужно, чтобы автомат принимал строки с чётным числом нулей.

Тогда:

$Q = \{q_0, q_1\}$
$$q_0$$ — чётное число нулей
$$q_1$$ — нечётное число нулей
$F = \{q_0\}$
Функция переходов $\delta$ :

Текущее состояние	Вход	Следующее состояние
$$q_0$$	0	$$q_1$$
$$q_0$$	1	$$q_0$$
$$q_1$$	0	$$q_0$$
$$q_1$$	1	$$q_1$$

Пример работы:

Для слова 10010:

q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1

Последнее состояние $q_1 \notin F$ , значит строка не принимается (нечётное число нулей).

Диаграмма переходов (Mermaid)

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : 0
    q0 --> q0 : 1
    q1 --> q0 : 0
    q1 --> q1 : 1
    q0 : чётное (принимающее)
    q1 : нечётное

Недетерминированный конечный автомат (НКА)

НКА также задаётся пятёркой:

A = (Q, \Sigma, \delta, q_0, F)

но функция переходов другая:

\delta: Q \times \Sigma \to 2^Q

То есть из одного состояния может быть несколько переходов по одному символу.

Автомат принимает строку, если существует хоть один путь из $$q_0$$ в $$F$$ , который соответствует этой строке.

$\varepsilon$ -переходы

Иногда автомат может переходить без чтения символа (на пустом входе):

\delta(q, \varepsilon) = q'

Это $\varepsilon$ -переход — изменение состояния без входных данных.

Связь между НКА и ДКА

Любой НКА можно преобразовать в эквивалентный ДКА (алгоритм построения подмножеств).

Идея:

Каждое состояние ДКА = множество состояний НКА.
Новая функция переходов $\delta'$ строится как объединение переходов всех элементов множества.

Язык, распознаваемый автоматом

Если автомат принимает строку $$w$$ , пишут:

A(w) = \text{accept}

Язык, который распознаёт автомат $$A$$ :

L(A) = \{ w \in \Sigma^* \mid A(w) = \text{accept} \}

То есть все слова, которые автомат принимает.

Регулярные языки и автоматы

Все языки, которые можно описать конечным автоматом, — регулярные языки.

Эквивалентно:

можно задать автоматом;
можно записать регулярным выражением;
можно описать регулярной грамматикой.

Минимизация автомата

Можно уменьшить количество состояний, не меняя язык:

Удалить недостижимые состояния
Объединить эквивалентные — ведущие себя одинаково для всех входов.

Результат — минимальный автомат.

Пример задачи

Задача: Построить автомат, принимающий строки над $\{a, b\}$ , оканчивающиеся на ab.

Решение:

Состояния:

$$q_0$$ — старт
$$q_1$$ — последнее было a
$$q_2$$ — последнее ab (принимающее)

Переходы:

$\delta(q_0, a) = q_1$
$\delta(q_0, b) = q_0$
$\delta(q_1, a) = q_1$
$\delta(q_1, b) = q_2$
$\delta(q_2, a) = q_1$
$\delta(q_2, b) = q_0$

$F = \{q_2\}$

Диаграмма автомата для “оканчивается на ab”

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : a
    q0 --> q0 : b
    q1 --> q1 : a
    q1 --> q2 : b
    q2 --> q1 : a
    q2 --> q0 : b
    q2 : принимающее

Символьная сводка

Обозначение	Значение
$$Q$$	множество состояний
$\Sigma$	алфавит
$\delta$	функция переходов
$$q_0$$	начальное состояние
$$F$$	множество допускающих состояний
$w = a_1 a_2 \dots a_n$	входная строка
$\Sigma^*$	множество всех строк из $\Sigma$
$\varepsilon$	пустая строка

Сводка

ДКА = $(Q, \Sigma, \delta, q_0, F)$
НКА = то же, но $\delta$ даёт множество состояний
$$L(A)$$ — язык, который автомат принимает
Все автоматы → регулярные языки
Можно минимизировать
Можно преобразовать НКА → ДКА
Принимает строку = путь из $$q_0$$ в $$F$$ по всем символам

Текущее состояние	Вход	Следующее состояние
$\(q_0\)$	0	$\(q_1\)$
$\(q_0\)$	1	$\(q_0\)$
$\(q_1\)$	0	$\(q_0\)$
$\(q_1\)$	1	$\(q_1\)$

Обозначение	Значение
$\(Q\)$	множество состояний
$\Sigma$	алфавит
$\delta$	функция переходов
$\(q_0\)$	начальное состояние
$\(F\)$	множество допускающих состояний
$w = a_1 a_2 \dots a_n$	входная строка
$\Sigma^*$	множество всех строк из $\Sigma$
$\varepsilon$	пустая строка