Начальное состояние автомата
Начальное состояние автомата — это состояние конечного автомата, в котором он находится до чтения первого символа входного слова. Из него начинается обработка слова и выполняется первый переход.
Как оно используется
Конечный автомат последовательно читает символы слова слева направо. На каждом шаге он переходит из текущего состояния в следующее согласно функции переходов и прочитанному символу. Поэтому первый переход определяется парой: начальное состояние \(q_0\) и первый символ слова.
Здесь \(a_1a_2\dots a_n\) — входное слово, а \(q_0\) — начальное состояние. Если слово пустое, символов для чтения нет, поэтому автомат остаётся в \(q_0\). Результат обработки пустого слова определяется тем, является ли \(q_0\) заключительным состоянием.
Пусть автомат имеет состояния \(q_0\), \(q_1\) и \(q_2\), а начальным является \(q_0\). Для слова «аб» сначала автомат читает «а» и выполняет переход из \(q_0\), например в \(q_1\). Затем читает «б» и переходит из \(q_1\) в \(q_2\). Нельзя начинать обработку сразу с \(q_1\): это изменило бы работу автомата.
Начальное состояние — это не заключительное состояние. Начальное состояние задаёт старт обработки, а заключительное состояние участвует в проверке результата после чтения всего слова. Одно и то же состояние может одновременно быть начальным и заключительным.
Из какого состояния автомат начинает обработку любого входного слова?
Чтобы определить, принято ли слово, после всех переходов сравнивают последнее достигнутое состояние с условием принятия слова автоматом. Начальное состояние важно учитывать и для пустого слова, и для первого перехода.
Главное
- Начальное состояние — состояние автомата до чтения первого символа; обычно оно обозначается \(q_0\).
- Обработка каждого слова начинается из \(q_0\), в том числе обработка пустого слова.
- Начальное и заключительное состояния имеют разные роли, хотя иногда могут совпадать.