Построение графа состояний
Прежде всего, определим набор состояний, исходя из различных реакций на прочитанный символ.
Вот полный перечень вариантов реакций:
- Символ буква: инициализировать обработку слова (счетчику длины слова присвоить единицу).
- Символ буква: продолжить обработку слова (счетчик длины слова увеличить на единицу).
- Символ не буква: закончить обработку слова (напечатать длину прочитанного слова).
- Символ не буква: пропустить символ.
- Символ конец строки: закончить обработку слова (напечатать длину прочитанного слова).
- Символ конец строки: пропустить символ.
- Символ конец строки: завершить процесс.
Есть еще одно действие, не отраженное в этом списке, но подразумеваемое: стандартное действие, происходящее перед началом отработки нового состояния. В данном случае это чтение очередного символа, которое должно выполняться, когда переход срабатывает. В других случаях автоматных моделей роль чтения очередного символа может играть, скажем, последующий шаг моделирования. Для данного и для большинства других автоматных примеров стандартное действие не нужно указывать явно, поскольку оно автоматически сопоставляется каждому переходу и полностью соответствует математической модели.
Из перечня действий для рассматриваемой задачи следует, что должно быть, как минимум, два класса состояний, имеющие разные действия-реакции.
Следующий методический прием - это определение начального состояния, т. е. того, в котором вычислительный процесс активизируется. Нужно указать, какие действия возможны в данном состоянии и какие условия перехода в нем должны быть.
Для рассматриваемого случая в начальном состоянии (St1), возможны переходы:
- с переходом в другое состояние - St2 (поскольку следующая буква требует другой реакции),
- с сохранением состояния и
- отработка первого перевода строки.
Рис. 9.4. Начало построения графа состояний по Муру
Результат только что проведенного анализа можно представить в виде графа, изображенного на рис. 9.4. С каждой дугой графа связано условие перехода. С каждым состоянием может быть связано действие.
В состояниях St1 и St3 действием является пропуск очередного символа и чтение следующего, но соединить их сейчас нельзя, поскольку в первом из них переход на завершение работы невозможен, так что перевод строки анализируется по-разному. Это позволяет предположить, что в данной задаче действия стоит ассоциировать с переходами, а не с состояниями. Правильный выбор того, с чем ассоциировать действия, может сильно оптимизировать программу. Для показа двух возможных вариантов, которые в данном случае почти эквивалентны по сложности, мы будем действовать как на переходах, так и в состояниях. В частности, предварительный анализ состояний при методе преобразований на переходах дан на рис. 9.5.
Рис. 9.5. Начало построения графа состояний при использовании метода на переходах
Внимание!
Если у Вас есть две близкие, но концептуально противоречивые, модели, в начале развития программы нужно сделать выбор в пользу одной из них. Небольшие эксперименты и отступления в начале оборачиваются большой экономией сил в конце.
На схемах вход и выход обозначаются черными прямоугольными блоками. При желании их можно считать специальными состояниями, с которыми ассоциированы действия инициализации и завершения процесса. Состояние St2 изображено штриховой линией, поскольку анализ его еще не проведен. Для каждого из еще не проанализированных состояний (в данном случае для St2) следует определить условия перехода (и соответствующие им действия, если выбрали работу на переходах).
В рассматриваем случае в состоянии St2 возможны переходы:
- с сохранением состояния;
- окончание слова и отработка вывода слова, поскольку следующий символ не буква, с переходом в другое состояние, которому дается временное имя St4;
- отработка окончания слова и перевода строки, ему можно дать временное имя St5.
После этого построения проверяется, не является ли новое состояние копией уже имеющихся как по действиям, так и по переходам. Если это так, то новое состояние можно отождествить (склеить) с одним из ранее построенных.
Вновь появляющиеся состояния анализируются аналогично.
Для решаемой задачи легко выяснить, что состояние St3 требует тех же действий и переходов, что и St5, а St4 изоморфно St1. Следовательно, возможна склейка этих двух состояний со старыми и построение графа завершается, так как новых состояний нет (см. рис. 9.6). С тем, чтобы не дублировать действия <Завершить процесс>, можно определить еще одно, заключительное состояние, с выходом из которого будет ассоциировано это действие (один раз!).
Рис. 9.6. Полученный граф состояний при действиях на переходах
Аналогично можно поступить и когда мы работаем в состояниях. Здесь процесс удлиняется на один шаг, поскольку необходимо выделить завершение обработки слова в отдельное действие (причем в двух вариантах: после перевода строки и после других небуквенных символов). Полученный результат показан на рис. 9.7.
Рис. 9.7. Полученный граф состояний при действиях в состояниях
