ЕГЭОГЭ
Задания № 23, 24 · ЕГЭ

Условие принятия слова автоматом

Как конечный автомат решает, принять ли входное слово
2 мин чтенияСложность: Обновлено 29 сентября 2026

Условие принятия слова автоматом — это правило, по которому после чтения всех символов входного слова проверяют состояние, в котором оказался автомат. Слово принимается, если это состояние является заключительным; иначе слово отвергается.

Условие принятия слова автоматомТермин связан с английским accept — «принимать».
Конечный автомат принимает слово \(w\), если, начав работу в своём начальном состоянии и последовательно обработав все символы слова, он завершает работу в одном из заключительных состояний. Если конечное состояние не является заключительным, автомат отвергает слово.

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

У конечного автомата есть начальное состояние, переходы по символам алфавита и множество заключительных состояний. Обозначим через \(\delta^*(q_0,w)\) состояние, в которое автомат попадёт из начального состояния \(q_0\) после чтения всего слова \(w\).

\[w\text{ принимается }\Longleftrightarrow \delta^*(q_0,w)\in F\]1

Здесь \(F\) — множество заключительных состояний. Важно обработать всё слово: проверка состояния до чтения последнего символа ещё не определяет результат.

№
Пример

Пусть автомат начинает в состоянии \(q_0\), после чтения каждой буквы \(a\) меняет состояние: \(q_0\to q_1\to q_0\to q_1\). Заключительным является только \(q_1\). Для слова \(aaa\) последовательность состояний такова: \(q_0\to q_1\to q_0\to q_1\). После последнего символа автомат в \(q_1\), поэтому слово принимается. Для слова \(aa\) итоговое состояние \(q_0\), поэтому оно отвергается.

!
Не путайте

Заключительное состояние не обязано быть единственным и не обязано быть состоянием, в котором автомат останавливается раньше конца слова. Принятие проверяют только после чтения всех символов. Если заключительных состояний несколько, достаточно попасть в любое из них.

Проверьте себя

Автомат после чтения слова оказался в состоянии \(q_2\). Состояния \(q_1\) и \(q_3\) заключительные. Что происходит со словом?

Как проверять слово в задаче

  1. Записать начальное состояние.
  2. Читать символы слова слева направо и выполнять соответствующие переходы.
  3. После последнего символа определить итоговое состояние.
  4. Сравнить его с множеством заключительных состояний и записать «принято» или «отвергнуто».
Главное за минуту

Главное

  • Слово принимается, если после чтения всех его символов автомат находится в заключительном состоянии.
  • Формула критерия: \(\delta^*(q_0,w)\in F\).
  • Проверять нужно итоговое состояние, а не промежуточное.