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

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

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

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

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

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

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

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:

  1. CLOSED
  2. SYN_SENT
  3. SYN_RECEIVED
  4. ESTABLISHED
  5. FIN_WAIT
  6. CLOSED (завершение соединения)

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

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

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

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

  1. Ожидание запуска
  2. Набор воды
  3. Стирка
  4. Полоскание
  5. Отжим
  6. Готово

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

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

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

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

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

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

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

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

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

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

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

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$ — множество заключительных (допускающих) состояний

Как работает

  1. Автомат начинает в состоянии $q_0$
  2. Читает входное слово $w = a_1 a_2 \dots a_n$
  3. Для каждого символа $a_i$ применяет переход:
\[ q_{i+1} = \delta(q_i, a_i) \]
  1. После чтения всей строки, если конечное состояние $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} \} \]

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

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

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

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

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

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

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

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

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

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

Задача: Построить автомат, принимающий строки над ${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$ по всем символам