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

5.7.1. Дерево состояний

Построение дерева состояний рассмотрим на примере простой среды. Среда и дерево состояний среды для нас не различимы. Если дерево состояний построено, то по нему можно построить автомат, который в этом случае также адекватен среде. Поэтому мы сразу будем говорить не о среде, а о дереве состояний и автомате, помня при этом, что речь все-таки идет об объектах, в определенной степени адекватных среде. Итак, пусть требуется построить автомат М, адекватный некоторой среде и имеющий один двоичный вход х и один двоичный выход На вход этого автомата (воздействие на среду) поступает произвольная бесконечная последовательность нулей и единиц, т.е. входной алфавит Каждая подпоследовательность подряд идущих входных символов входной бесконечной последовательности поступает на вход автомата соответственно в моменты времени где — некоторый момент времени; — момент времени, предшествующий моменту — момент времени, предшествующий моменту — момент времени, предшествующий моменту Каждая такая подпоследовательность рассматривается как четырехразрядное двоичное число (т. е. это число подается на вход автомата, начиная со старших разрядов). Задачей автомата М является классификация десятичных эквивалентов подпоследовательностей подаваемых на его вход соответственно в моменты времени на две группы: меньших или равных 9 и больших 9. На выходе автомата должен появляться 0 в первом случае и 1 — во втором.

Отметим, что рассматриваемый автомат является представителем обширного класса автоматов, принадлежащих к декодирующим устройствам, задачей которых является обнаружение во входной бесконечной последовательности, подаваемой на их входы, некоторых подпоследовательностей, обладающих тем или иным свойством. Для практических задач естественно считать, что автомат, прежде чем начать свою работу; находится в некотором начальном состоянии, через которое он может многократно проходить в процессе своей работы. Пусть для рассматриваемого автомата М это будет состояние Очевидно, что существует всего 24 различные входные последовательности длиной 4. Учитывая сказанное, дерево состояний автомата можно строить следующим образом. Будем полагать, что в начальном состоянии находящемся на ярусе 0 дерева, нам неизвестны значения переменных (неизвестные значения переменных обозначим знаком ), которые подавались на вход автомата в предыдущие моменты времени. Состояния — последователи начального состояния (начальное состояние находится на ярусе 0) получаются в результате действия, присваивающего переменной одно из возможных значений (0 или 1). В результате имеем состояния яруса 1. Последователи состояний яруса 1 получаются в результате

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

Рис. 5.10. (см. скан) Дерево поиска состояний автомата М

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

5.7.2. Построение неминимального графа переходов

Для того чтобы можно было от построенного дерева на рис. 5.10 перейти к неминимальному графу переходов, будем полагать, что нам известна подпоследовательность в результате которой автомат попал в состояние Вообще это может бьггь любая подпоследовательность из числа допустимых. Пусть это будет подпоследовательность 0000. Тогда во всех подпоследовательностях дерева, показанного на рис. 5.10, символ следует заменить на 0. В результате получим дерево, показанное на рис. 5.11. Каждой вершине этого дерева соответствует одна конкретная подпоследовательность состоящая из 0 и 1. Все конкретные подпоследовательности встречаются на дереве. Дерево, представленное на рис. 5.10, может быть продолжено, поскольку на автомат подаемся бесконечная последовательность из и 1. Но новых подпоследовательностей и соответствующих им состояний уже не появится. Для каждого из состояний на дереве рис. 5.10, из которого дуги не выходят, найдется уже полученное состояние, в которое из этого состояния может быть направлена дуга. Поэтому нет смысла продолжать построение дерева, а во-вторых, можно удалить те поддеревья, которые начинаются в состояниях, встречающихся повторно, перенаправив идущие к этим поддеревьям дуги в ранее встречающиеся состояния. В результате из дерева на рис. 5.11 получится граф переходов, показанный на рис. 5.12.

Рис. 5.11. Дерево поиска состояний после конкретизации начальной последовательности

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

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

5.7.3. Минимизация числа состояний

Перейдем теперь к минимизации числа состояний автомата, показанного на рис. 5.12, по алгоритму детерминизации по множеству состояний. На рис. 5.13 — 5.16 показаны совокупности классов состояний полученные по этому алгоритму. В соответствии с классами после переобозначений классов символами состояний получаем автомат, граф переходов которого показан на рис. 5.17.