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

Граф переходов представляет собой структуру, состоящую из вершин, изображаемых в виде малых кружков, и ориентированных дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. Граф переходов, описывающий автомат с n состояниями, содержит n вершин, причем каждая вершина соответствует одному состоянию автомата; состояние, изображаемое вершиной, снабжается обозначением, соответствующим этому состоянию. Ориентированные дуги проводятся и обозначаются по следующему правилу. Пусть X_ij = {ξk_1, ξk₂,..., ξk_f} представляет собой множество значений xv, для которых f_s(x_v, σ_i) = σ_j, и пусть f _z(ξ k_h,σ _i) = ξ i_h для h =1, 2,..., r. Если Х_ij не пустое[10] множество, то дуга проводится из вершины σ _i в вершину σ _j, стрелка указывает направление из σ _i в σ _j и обозначение дуги записывается в виде

[11]

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

По построению графа дуга, направленная из вершины σ _i к вершине σ _j, обозначается входными символами, которые вызывают переход автомата из состояния σ _i в σ _j, и выходными символами, которые выдаются автоматом при этом переходе. Для детерминированного, без ограничений на входе автомата каждый входной сигнал вызывает переход из каждого состояния только в одно другое состояние; следовательно, дуги, выходящие из любой данной вершины, содержат полное число р пар вход-выход, где р — мощность входного алфавита. Непосредственное преимущество графа переходов состоит в том, что он облегчает определение реакции автомата на входную последовательность любой длины. При данном начальном состоянии at автомата М и входной последовательности ξu₁, ξu₂,..., ξu _l реакция М легко определяется прослеживанием (в направлении стрелок) непрерывной последовательности l дуг, которая начинается в вершине σ _i и k-я дуга которой (k = 1, 2,..., l) соответствует паре вход-выход (ξu _k /ξv _k). Выходная последовательность, которую выдает автомат М при подаче на него входной последовательности ξu₁, ξu₂,..., ξu _l, тогда будет ξv₁, ξv₂,..., ξv _l, состояние, в которое при этом переходит М, определяется по обозначению вершины, в которой заканчивается последовательность из / дуг. Например, реакция автомата А\ на входную последовательность πunλλdπ при начальном состоянии 3 легко определяется по рис. 2.2 и будет 0000001. Последовательность состояний при этом будет 1, 3, 4, 4, 4, 5 и 1.

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

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