Построение графа состояний
Прежде всего, определим набор состояний, исходя из различных реакций на прочитанный символ.
Вот полный перечень вариантов реакций:
- Символ буква: инициализировать обработку слова (счетчику длины слова присвоить единицу).
- Символ буква: продолжить обработку слова (счетчик длины слова увеличить на единицу).
- Символ не буква: закончить обработку слова (напечатать длину прочитанного слова).
- Символ не буква: пропустить символ.
- Символ конец строки: закончить обработку слова (напечатать длину прочитанного слова).
- Символ конец строки: пропустить символ.
- Символ конец строки: завершить процесс.
Есть еще одно действие, не отраженное в этом списке, но подразумеваемое: стандартное действие, происходящее перед началом отработки нового состояния. В данном случае это чтение очередного символа, которое должно выполняться, когда переход срабатывает. В других случаях автоматных моделей роль чтения очередного символа может играть, скажем, последующий шаг моделирования. Для данного и для большинства других автоматных примеров стандартное действие не нужно указывать явно, поскольку оно автоматически сопоставляется каждому переходу и полностью соответствует математической модели.
Из перечня действий для рассматриваемой задачи следует, что должно быть, как минимум, два класса состояний, имеющие разные действия-реакции.
Следующий методический прием - это определение начального состояния, т. е. того, в котором вычислительный процесс активизируется. Нужно указать, какие действия возможны в данном состоянии и какие условия перехода в нем должны быть.
Для рассматриваемого случая в начальном состоянии (St1), возможны переходы:
- с переходом в другое состояние - St2 (поскольку следующая буква требует другой реакции),
- с сохранением состояния и
- отработка первого перевода строки.
Рис. 9.4. Начало построения графа состояний по Муру
Результат только что проведенного анализа можно представить в виде графа, изображенного на рис. 9.4. С каждой дугой графа связано условие перехода. С каждым состоянием может быть связано действие.
