Стили и методы программирования

     osb плита купить |       

Построение графа состояний


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

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

  1. Символ буква: инициализировать обработку слова (счетчику длины слова присвоить единицу).
  2. Символ буква: продолжить обработку слова (счетчик длины слова увеличить на единицу).
  3. Символ не буква: закончить обработку слова (напечатать длину прочитанного слова).
  4. Символ не буква: пропустить символ.
  5. Символ конец строки: закончить обработку слова (напечатать длину прочитанного слова).
  6. Символ конец строки: пропустить символ.
  7. Символ конец строки: завершить процесс.

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

Из перечня действий для рассматриваемой задачи следует, что должно быть, как минимум, два класса состояний, имеющие разные действия-реакции.

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

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

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


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

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

Содержание  Назад  Вперед




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий