Задание автомата графом переходов

Представление автоматов графом переходов называется также графическим представлением. При этом способе автомат задается графом переходов (ГП). Граф переходов – ориентированный граф, вершины которого соответствуют состояниям автомата, а дуги – переходам. Две вершины a _m и a _s соединяются дугой, если в автомате имеется переход из a _m в a _s. Дуга отмечается входным сигналом x _f и выходным сигналом y _g.

Если выходной сигнал не определен, ставится прочерк (тире). Максимальное количество дуг, выходящих из вершины графа, равно числу букв входного алфавита.

Если переход из состояния a _m в состояние a _s вызывается многими входными сигналами, то дуги отмечаются всеми этими сигналами.

Автомат Мура задается графом переходов, в котором выходной сигнал записывается внутри вершины или рядом с ней.

На рис.4.3, 4.4 и 4.5 изображены графы переходов автомата Мили, Мура и С-автомата соответственно.