Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 8

Прежде всего, определим набор состояний, исходя из различных реакций на прочитанный символ.

Вот полный перечень вариантов реакций:

1.  Символ буква: инициализировать обработку слова (счетчику длины слова присвоить единицу).

2.  Символ буква: продолжить обработку слова (счетчик длины слова увеличить на единицу).

3.  Символ не буква: закончить обработку слова (напечатать длину прочитанного слова).

4.  Символ не буква: пропустить символ.

5.  Символ конец строки: закончить обработку слова (напечатать длину прочитанного слова).

6.  Символ конец строки: пропустить символ.

7.  Символ конец строки: завершить процесс.

Есть еще одно действие, не отраженное в этом списке, но подразумеваемое: стандартное действие, происходящее перед началом отработки нового состояния. В данном случае это чтение очередного символа, которое должно выполняться, когда переход срабатывает. В других случаях автоматных моделей роль чтения очередного символа может играть, скажем, последующий шаг моделирования. Для данного и для большинства других  примеров  построения конечных автоматов, стандартное действие чтение очередного символа не нужно указывать явно, поскольку оно автоматически сопоставляется каждому переходу и полностью соответствует математической модели.

Из анализа  рассматриваемой задачи следует, что должно быть, как минимум, два класса состояний, имеющие разные действия-реакции: начальное состояние и конечное состояние. Обозначим эти состояния соответственно St1 и St2 .  Для каждого состояния  необходимо определить :  1)какие действия возможны в данном состоянии и 2) какие условия перехода в нем должны быть.

Для рассматриваемого случая в начальном состоянии (St1), возможны следующие сторожевые условия перехода:

1.  символ буква: реакция - переход в другое состояние - St2 (поскольку следующая буква требует другой реакции); действие – начать обработку слова;

2.  символ не буква: реакция – остаться в исходном состоянии; действие – пропустить символ.

3.  символ первого перевода строки: реакция - переход в другое состояние – St3 (поскольку следующий символ перевода  требует другой реакции); действие – пропустить символ.

В состоянии  (St3), возможны следующие сторожевые условия перехода:

4.  символ буква: реакция - переход в другое состояние - St2 (поскольку следующая буква требует другой реакции); действие – начать обработку слова;

5.  символ не буква: реакция – перейти в  состояние St1 ; действие – пропустить символ.

6.  символ первого перевода строки: реакция - переход в другое состояние – конечное; действие – завершить процесс.

Результат только что проведенного анализа можно представить в виде графа, изображенного на рис. 3. С каждой дугой графа связано условие перехода.

    С каждым состоянием может быть связано действие. В состояниях St1 и St3 действием является пропуск очередного символа и чтение следующего, но соединить их сейчас нельзя, поскольку в первом из них переход на завершение работы невозможен, так что перевод строки анализируется по-разному. Это позволяет предположить, что в данной задаче действия стоит ассоциировать с переходами, а не с состояниями. Правильный выбор того, с чем ассоциировать действия, может сильно оптимизировать программу. Ниже приведены возможные варианты, которые в данном случае почти эквивалентны по сложности. Рассмотрим случай, когда действия автомата ассоциируются с переходами.

Рис. 3  Начало построения графа состояний  без учёта действий автомата

На рис 4 приведён фрагмент конечного автомата, в котором преобразования ассоциируются с переходами ( автомат Мили).

Рис. 4  Начало построения графа состояний по Мили

          На схемах вход и выход обозначаются черными прямоугольными блоками. При желании их можно считать специальными состояниями, с которыми ассоциированы действия инициализации и завершения процесса. Состояние St2 изображено штриховой линией, поскольку анализ его еще не проведен. Для каждого из еще не проанализированных состояний (в данном случае для St2) следует определить условия перехода (и соответствующие им действия, если выбрали работу на переходах).

В состоянии St2 возможны переходы:

7.  символ буква: реакция – остаться в исходном состоянии - St2; действие – продолжить обработку слова;

8.  символ не буква: реакция – перейти в новое состояние St4; действие – закончить обработку слова.

9.  символ первого перевода строки: реакция - переход в другое состояние – St5; действие – пропустить символ.

Вновь появляющиеся состояния анализируются аналогично. После этого построения проверяется, не является ли новое состояние копией уже имеющихся состояний, как по действиям, так и по переходам. Если это так, то новое состояние можно отождествить (склеить) с одним из ранее построенным состоянием.

Для решаемой задачи легко выяснить, что состояние St5 требует тех же действий и переходов, что и St3, а St4 изоморфно St1. Следовательно, возможна склейка этих двух состояний со старыми состояниями и построение графа завершается, так как новых состояний нет (см. рис. 5). Если на переходах действия не определены (см. рис.5), то выполняются действия по умолчанию: пропустить символ см. замечание выше.

Рис. 5  Полученный граф состояний Мили – действия определены  на переходах

Аналогично можно поступить, когда мы проектируем решение задачи, используя модель Мура. Здесь процесс удлиняется на один шаг, поскольку необходимо выделить завершение обработки слова в отдельное действие (причем в двух вариантах: после перевода строки и после других небуквенных символов). Полученный результат показан на рис. 6.

Рис. 6.  Полученный граф состояний Мура – действия определены в состояниях