Задания № 16, 27 · ЕГЭ

Распознавание слова конечным автоматом

Как конечный автомат проверяет, принадлежит ли слово заданному языку

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

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

Как выполняется проверка

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

\[q_0 \xrightarrow{a_1} q_1 \xrightarrow{a_2} q_2 \xrightarrow{a_3} \dots \xrightarrow{a_n} q_n\]

Здесь $q_0$ — начальное состояние, $a_1, a_2, \dots, a_n$ — символы слова, а $q_n$ — состояние после обработки всего слова. Если для очередного символа переход не задан, слово сразу не принимается.

№

Пример

Пусть начальное состояние $q_0$, допускающее состояние $q_2$, а переходы таковы: из $q_0$ по символу «а» перейти в $q_1», из$q_1$по символу «б» — в$q_2$. Для слова «аб» получаем цепочку$q_0 \xrightarrow{а} q_1 \xrightarrow{б} q_2$. Конечное состояние допускающее, значит, слово принято. Для слова «аа» второй переход может отсутствовать, поэтому слово отвергается.

Не перепутайте

Автомат проверяет не отдельные символы по одному, а всю последовательность переходов. Важно также не останавливаться при попадании в допускающее состояние: если символы ещё остались, их нужно обработать. Распознавание — одна из задач, решаемых в модели конечного автомата.

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

Автомат закончил чтение слова в недопускающем состоянии. Каков результат?

Главное за минуту

Главное

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