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


Автоматные задачи - часть 2


Такие процедуры назовем действиями.

Таблицы автоматов часто также представляются в виде графов, что особенно удобно, когда не все возможные переходы между состояниями реализуемы. См., напр., рис. 9.1, где представлены и таблица, и граф.

Таблица состояний. Граф переходов.

Рис. 9.1.  Таблица состояний. Граф переходов.

Здесь состояния идентифицируются порядковыми номерами, а воздействия - буквами.

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

Имеется вариация понятия автоматов, порождающая другой метод автоматного программирования. В теории автомат Мили отличается тем, что результат, записываемый на выходную ленту автомата, может зависеть от выбранного перехода. На практике действия в таблице состояний и переходов могут ассоциироваться либо с состояниями (с вершинами графа, автомат Мура), либо с переходами (с дугами графа, автомат Мили). Ниже Вы увидите примеры, когда при программировании естественно возникают оба этих варианта2). Модель вычислений автомата Мили лучше использовать, если проверки в каждом состоянии по существу различны, а модель автоматов Мура - если проверки по существу однородны, как в примере 9.1.1.Метод программирования, когда действия сопоставляются переходам, назовем преобразованиями на переходах (сокращенно просто "на переходах"), метод, когда действия производятся в состояниях, назовем преобразованиями в состояниях (сокращенно просто "в состояниях").

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

Внимание!

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


Начало  Назад  Вперед