Автомат с тремя исходными состояниями

Пример определения эквивалентных состояний автомата

Понятие эквивалентности

С практической точки зрения при функционировании автомата представляет интерес, в основном, зависимость между входами и выходами автомата. В этом случае роль автомата сводится к формированию этих зависимостей и любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состояний автомата.

Эта возможность привела к одной из важных задач теории конечных автоматов – минимизации автоматов, заключающаяся в сокращении числа состояний путем объединения эквивалентных состояний.

Состояния называются эквивалентными, если поведение автомата одинаково независимо от того, какое из них является исходным.

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

Эквивалентные автоматы неразличимы по реакции на выходе, но могут иметь различное количество внутренних состояний, и, следовательно, могут отличаться внутренними состояниями при одинаковых входных данных.

Для определения эквивалентных состояний используется понятие «k – эквивалентности».

Состояние называется k‑эквивалентным, если автомат, находясь в любом из них, имеет одинаковое поведение в течение k тактов. k‑эквивалентные состояния образуют k-эквивалентные классы.

Очевидно, что при малых k число k-эквивалентных состояний больше, чем при больших k (а число k-эквивалентных классов меньше). Это позволяет указать путь определения эквивалентных состояний. Он заключается в разбиении состояний автомата на k‑эквивалентные классы поочередно для k = 1,2,3…. Число таких классов постепенно растет, размер классов уменьшается, и в итоге в них останутся только эквивалентные состояния. Классы, которые невозможно разбить являются классами эквивалентных состояний.

Автомат представлен в виде графа (рис.1.5.1). Определим, есть ли у автомата эквивалентные состояния.

Рис. 1.5.1 Представление автомата в виде графа

Графу соответствует таблица переходов (табл. 1.5.1).

Таблица 1.5.1

Произведем первое разбиение автомата, которое приведено в табл. 1.5.2.

Таблица 1.5.2

Состояния 1 и 3 объединены в один класс, поскольку на любое входное воздействие автомат при этих состояниях реагирует одинаково (состояния не различаются по выходам).

Из табл. 1.5.2 видно, что дальнейшее разбиение невозможно, поскольку при любом входе состояния 1 и 3 одного класса, который только и можно разбить, переходят в состояние одного класса (либо 1, либо 2), которые неразличимы.

Таким образом, автомат можно упростить и представить в виде графа (рис. 1.5.2) и таблицы переходов (табл. 1.5.3.).

Рис. 1.5.2 Граф минимизированного автомата

Таблица 1.5.3