Таблица переходов автомата
Таблица переходов автомата — компактная запись, показывающая, как исполнитель изменяет своё состояние при чтении очередного символа входного слова. Научившись правильно заполнять и читать такую таблицу, можно решать задачи на моделирование конечного автомата, обработку слов и подсчёт возможных состояний.
Основные понятия
Автомат получает входное слово по одному символу. В каждый момент он находится в одном из заранее заданных состояний. После чтения очередного символа автомат либо переходит в другое состояние, либо остаётся в прежнем. Результат перехода определяется правилом, записанным в таблице.
Состояние — это информация о текущем положении автомата, достаточная для выбора дальнейшего перехода. Состояния обычно обозначают числами, латинскими буквами или короткими словами: \(q_0\), \(q_1\), \(A\), \(B\).
Таблица переходов — таблица, в которой строки соответствуют текущим состояниям, столбцы — возможным входным символам, а в ячейке записано состояние, в которое перейдёт автомат после чтения символа.
В задачах часто дано описание перехода между состояниями в виде фразы: «Если автомат находится в состоянии 2 и получает символ 0, он переходит в состояние 3». В таблице это означает: в строке 2 и столбце 0 нужно записать 3.
Здесь \(q\) — текущее состояние, \(a\) — прочитанный символ, \(q'\) — новое состояние, а \(\delta\) — функция переходов. В обычном детерминированном автомате для каждой пары «состояние и символ» существует ровно один результат.
Как читать таблицу переходов
Внешний вид таблицы может немного отличаться, но смысл одинаков. Например, для алфавита \(\{0,1\}\) таблица может иметь вид:
| Текущее состояние | Символ 0 | Символ 1 |
|---|---|---|
| \(A\) | \(B\) | \(A\) |
| \(B\) | \(C\) | \(A\) |
| \(C\) | \(C\) | \(B\) |
Чтобы выполнить один шаг, нужно найти строку текущего состояния, затем выбрать столбец прочитанного символа. Пересечение строки и столбца даст новое состояние. Например, из \(B\) по символу \(0\) автомат переходит в \(C\), а из \(C\) по символу \(1\) — в \(B\).
- Определите начальное состояние автомата.
- Возьмите первый символ слова.
- Найдите строку, соответствующую текущему состоянию.
- В этой строке выберите столбец прочитанного символа.
- Запишите новое состояние и повторите действия для следующего символа.
После обработки всего слова конечное состояние получают последовательным применением функции переходов: сначала обрабатывают первый символ, затем второй и так далее. Нельзя перескакивать через символы или менять их порядок.
Если слово имеет вид \(a_1a_2\ldots a_n\), то состояние после его обработки обозначают \(\delta^*(q_0,a_1a_2\ldots a_n)\). Звёздочка означает применение переходов ко всему слову, а не к одному символу.
Эта запись удобна для решения вручную: \(q_0\) — начальное состояние, \(a_i\) — очередной символ, \(q_i\) — состояние после его обработки.
Автомат находится в состоянии \(B\) и читает символ \(1\). Что делать по таблице выше?
Как составить таблицу по условию
Если таблица не дана, её строят по описанию алгоритма. Сначала выписывают все состояния и символы входного алфавита. Затем для каждой пары «состояние — символ» находят результат перехода. Важно проверить все клетки: пропущенная клетка означает, что автомат не определён для соответствующей ситуации.
Заполняйте таблицу построчно: выберите одно состояние и последовательно рассмотрите все возможные символы. После этого переходите к следующей строке. Так меньше риск перепутать текущее и новое состояние.
Иногда переход обозначают стрелкой, например \(2\xrightarrow{a}3\). Это означает то же самое, что и запись \(\delta(2,a)=3\). Петля \(2\xrightarrow{b}2\) означает, что по символу \(b\) автомат остаётся в состоянии 2.
Если автомат должен обрабатывать любой символ из алфавита в любом состоянии, в таблице должна быть заполнена каждая клетка. Для \(m\) состояний и алфавита из \(k\) символов требуется \(m\cdot k\) переходов.
В некоторых задачах встречается не один результат, а несколько возможных переходов. Тогда автомат недетерминированный, и обычной записи с одним числом в каждой клетке уже недостаточно. В школьных задачах чаще используется детерминированный вариант.
Разобранный пример: обработка слова
Автомат имеет состояния \(0\), \(1\) и \(2\), начальное состояние \(0\). Таблица переходов задана так: по символу \(0\) из состояний \(0\), \(1\), \(2\) автомат переходит соответственно в \(1\), \(2\), \(0\); по символу \(1\) — соответственно в \(0\), \(0\), \(2\). Найдите состояние автомата после обработки слова \(0101\).
Сначала составим таблицу, чтобы не потерять ни одного правила.
| Состояние | 0 | 1 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2 | 0 |
| 2 | 0 | 2 |
Теперь обрабатываем слово слева направо. Начальное состояние — \(q_0=0\). На каждом шаге используем текущую строку и столбец очередного символа.
Показать ответ Решение
После обработки слова \(0101\) автомат находится в состоянии \(0\). Последовательность состояний: \(0\to1\to0\to1\to0\).
Такая запись полезна и для задач на обработку слова конечным автоматом. Если требуется определить, принимает ли автомат слово, после последнего символа сравнивают итоговое состояние с множеством допускающих состояний. Подробные задачи на это рассматриваются в теме распознавания слова конечным автоматом.
Типичные задачи и ошибки
Таблица переходов встречается не только в прямом моделировании. По ней могут просить восстановить неизвестную клетку, найти слово, приводящее в заданное состояние, определить число шагов или проверить утверждение о работе автомата. В задачах ЕГЭ важно внимательно различать начальное состояние, текущее состояние и состояние после перехода.
- Для поиска состояния после слова последовательно просматривайте символы слева направо.
- Для восстановления перехода используйте строку текущего состояния и столбец входного символа.
- Для проверки нескольких слов запоминайте только текущее состояние, а не всю историю переходов.
- Если нужно получить количество переходов, оно равно длине обработанного слова.
1. Начинают не с начального состояния, а с первой строки таблицы. 2. Читают слово справа налево. 3. Выбирают строку нового состояния вместо текущего. 4. Путают символ, по которому выполняется переход, с номером состояния. 5. После последнего символа делают ещё один переход без основания. 6. Считают состояние начальным только потому, что оно обозначено нулём: начальное состояние должно быть явно задано.
В задачах, связанных с перебором, таблица переходов может быть частью большого дерева вариантов. Тогда полезно применять правило отсечения ветвей: если дальнейшие переходы уже не могут привести к нужному результату, такую последовательность не рассматривают.
Таблица читается по паре: текущее состояние + входной символ. Ячейка на пересечении даёт следующее состояние. После обработки всего слова ответом является последнее полученное состояние.
Быстрая проверка
Итоги
- Таблица переходов связывает текущее состояние и входной символ с новым состоянием.
- Для обработки слова переходы выполняют строго слева направо, начиная с заданного начального состояния.
- Чтобы прочитать таблицу, выбирают строку текущего состояния и столбец очередного символа.
- Для автомата с \(m\) состояниями и алфавитом из \(k\) символов полная таблица содержит \(m\cdot k\) переходов.
- Главная проверка после решения — убедиться, что использованы все символы слова и последний переход выполнен именно по последнему символу.