2.5. Граф переходов

Граф переходов представляет собой структуру, состоящую из вершин, изображаемых в виде малых кружков, и ориентированных дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. Граф переходов, описывающий автомат с состояниями, содержит вершин, причем каждая вершина соответствует одному состоянию автомата; состояние, изображаемое вершиной, снабжается обозначением, соответствующим этому состоянию. Ориентированные дуги проводятся и обозначаются по следующему правилу. Пусть представляет собой множество значений для которых и пусть Если не пустое) множество, то дуга проводится из вершины в вершину , стрелка указывает направление из и обозначение дуги записывается в виде

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

Рис. 2.1. Обозначение дуги.

Рис. 2.2. Автомат

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

автомата каждый входной сигнал вызывает переход из каждого состояния только в одно другое состояние; следовательно, дуги, выходящие из любой данной вершины, содержат полное число p пар вход - выход, где p — мощность входного алфавита. Непосредственное преимущество графа переходов состоит в том, что он облегчает определение реакции автомата на входную последовательность любой длины. При данном начальном состоянии автомата М и входной последовательности реакция М легко определяется прослеживанием (в направлении стрелок) непрерывной последовательности дуг, которая начинается в вершине дуга которой соответствует паре вход - выход Выходная последовательность, которую выдает автомат М при подаче на него входной последовательности тогда будет состояние, в которое при этом переходит М, определяется по обозначению вершины, в которой заканчивается последовательность из дуг. Например, реакция автомата на входную последовательность при начальном состоянии 3 легко определяется по рис. 2.2 и будет 0000001. Последовательность состояний при этом будет 1, 3, 4, 4, 4, 5 и 1.

Роль графа переходов в теории конечных автоматов подобна роли, которую играет графическое изображение схемы в теории электрических цепей. Граф переходов преобразует абстрактную модель в физическое изображение, усиливающее интуицию исследователя, и дает возможность ему «отчетливо представить» различные процессы и свойства, которые без такого изображения остались бы рядом сухих математических фактов. Как и в теории цепей, граф переходов удобно рассматривать как модель саму по себе, а символы, используемые в графе, — как абстрактные компоненты модели. Поэтому часто в дальнейшем мы будем граф, представляющий автомат М, называть «автоматом Ж», вершину, представляющую состояние — «состоянием и, наоборот, отождествлять абстрактные понятия с их геометрическими представлениями, имеющимися в графе переходов.

Понятие изоморфизма конечных автоматов, введенное в § 2.4, в терминах графов переходов допускает очень

простую интерпретацию: автоматы изоморфны один другому, если они имеют одинаковые графы, отличающиеся, быть может, только обозначением вершин. Таким образом, для того чтобы автомат М заменить изоморфным ему автоматом, надо просто изменить обозначение одной или нескольких вершин. Аналогично, чтобы получить семейство перестановок автомата М, достаточно переставить обозначения вершин всеми возможными способами.