5.5. Граф переходов состояний среды

Вернемся теперь снова к примеру со средой кота из второй главы и рис. 2.2, на котором показано дерево переходов из начального состояния во все состояния этой среды. От этого дерева легко перейти к графу переходов, оставив только одну из повторяющихся вершин (ту, которая расположена ближе к начальному состоянию) и направив дугу в оставшуюся вершину. В результате получится граф переходов, показанный на рис. 5.4. На этом графе каждая вершина имеет петлю. Это означает, что при действии (действиях), соответствующем петле, состояние среды остается неизменным и такие действия желательно не осуществлять. Устраним их на графе, изображенном на рис. 5.4. В результате получим граф без петель, показанный на рис. 5.5. Зададим на множестве состояний этого графа функцию Будем полагать, что на целевых состояниях а на всех остальных Построим автомат М по последнему алгоритму. Получим классы

Рис. 5.4. Граф переходов с петлями для среды кота

Если по этим множествам построить граф переходов автомата он будет иметь два состояния и не будет детерминированным, поскольку подмножества состояний одного и того же класса переходят в состояния различных классов Поэтому по этим классам не может быть построен автомат и класс необходимо разбить на подклассы Если построить по этим классам автомат то он будет иметь три состояния, но опять не будет детерминированным, поскольку подмножества состояний одного и того же класса переходят в состояния различных классов Это видно на рис. 5, 7. Разобьем класс на два подкласса. В результате получим классы В соответствии с этими классами уже может быть построен детерминированный автомат М, Поскольку все состояния каждого из классов переходят в состояния какого-либо одного класса Это видно из рис. 5. 8.

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

(кликните для просмотра скана)