Заключительное состояние автомата
Заключительное состояние автомата — это состояние, в котором конечный автомат оказывается после обработки всех символов входного слова. По этому состоянию определяют, принято слово автоматом или нет.
Как находят заключительное состояние
Автомат читает слово слева направо, по одному символу. Для каждого символа выбирается переход из текущего состояния. После последнего символа полученное состояние и является заключительным. Затем его сравнивают с множеством принимающих состояний согласно условию принятия слова автоматом.
Здесь \(q_0\) — начальное состояние, \(w\) — обработанное слово, а \(\delta^*\) — последовательное применение переходов ко всем символам слова. Если \(q_{\text{зак}}\) принадлежит множеству принимающих состояний, слово принимается; иначе оно отвергается.
Пусть автомат начинает в состоянии \(q_0\) и имеет переходы: из \(q_0\) по символу 1 — в \(q_1\), из \(q_1\) по символу 0 — в \(q_2\), из \(q_2\) по символу 1 — в \(q_1\). Для слова 101 маршрут такой: \(q_0\xrightarrow{1}q_1\xrightarrow{0}q_2\xrightarrow{1}q_1\). Заключительное состояние — \(q_1\). Если \(q_1\) принимающее, слово 101 принимается.
Заключительное состояние — не обязательно конечная или «тупиковая» вершина, из которой нет выходов. Это просто состояние после последнего прочитанного символа. Если слово закончится раньше или позже, заключительное состояние может быть другим.
Автомат начал в \(q_0\) и прошёл по слову маршрут \(q_0\to q_2\to q_3\). Какое состояние является заключительным?
Главное
- Заключительное состояние получают после обработки всех символов слова.
- Оно зависит от начального состояния, слова и переходов автомата.
- Принятие слова определяется тем, является ли заключительное состояние принимающим.