Минимизация конечных автоматов

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

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

Определение 7. Два состояния p и q конечного автомата
A=S, X, Y, s0, δ, λ называются эквивалентными (обозначается p≈ q), если для любой цепочки α ∈ X* выполняется λ *p, α =λ *q, α.

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

Определение 7 не является конструктивным: оно не даёт процедуры выяснения того, являются ли два состояния эквивалентными, поскольку мы не можем перебрать все входные цепочки. Однако существует алгоритм определения максимального отношения эквивалентности на множестве состояний конечного автомата, который будет сейчас рассмотрен.

Определение 8. Состояния p и q конечного автомата A=S, X, Y, s0, δ, λ называются k-эквивалентными (обозначается p≈ kq, если они неразличимы любой цепочкой α ∈ X* длины k.

Алгоритм минимизации состоит в последовательном построении на множестве состояний автомата A цепочки разбиений π 0, π 1, … таких, что в один класс разбиения π k попадают k -эквивалентные состояния. Очевидно, что в любом автомате все состояния 0-эквивалентны (при подаче пустой цепочки на вход выходом также является пустая цепочка независимо от состояния автомата). Значит, π 0=S. Разбиение π 1 также легко построить. По определению, в один блок разбиения π 1 попадают те состояния, в которых автомат одинаково реагирует на входные сигналы: p≈ 1 q⇔ ∀ x∈ X λ (p, x)=λ (q, x). Разбиения π 0 и π 1 являются исходными при построении цепочки разбиений. Если мы сможем определить, как строить следующее разбиение из предыдущего, то начиная с π 1, мы сможем последовательно построить всю цепочку.

Теорема 2. Пусть p≈ kq, k> 1. Для того чтобы p≈ k+1q, необходимо и достаточно, чтобы ∀ x∈ X δ p, x≈ kδ q, x. Иными словами, для того, чтобы два k-эквивалентных состояния были бы (k+1)-эквивалентными, необходимо и достаточно, чтобы под воздействием любого входного сигнала автомат переходил из этих состояний в пару состояний, которые сами были бы k-эквивалентными.

Очевидно, что если p и q (k+1)-эквивалентны, то они k -эквивалентны. Иными словами, блоки разбиения π k+1 являются подблоками разбиения π k. Поскольку число состояний конечно, может быть только конечное число последовательно уменьшающихся разбиений π k, начиная с максимального разбиения π 0, содержащего единственный блок. Более того, очевидно, что их не больше, чем число состояний автомата. Однако построение уменьшающихся разбиений можно не продолжать дальше, как только два последовательных разбиения совпадают.

Теорема 3. Пусть π k+1=π k. Тогда для любого i> k π i=π k.

Рассмотрим процедуру минимизации на конкретном примере. Пусть имеется конечный автомат, заданный следующей таблицей функций δ и λ.

Будем последовательно строить разбиения его состояний.

– π 0=1, 2, 3, 4, 5, 6, 7, 8, 9. Это тривиальное разбиение, оно состоит из одного элемента, включающего все состояния автомата.

– π 1=1, 3, 5, 6, 8, 9, 2, 4, 7. Автомат, который находится в состоянии 1, генерирует для входных сигналов комбинацию выходов (1, 0), которая совпадает с комбинациями для состояний 3, 5, 6, 8, 9. Поэтому данные состояния являются 1-эквивалентными и объединяются в один класс A1=1, 3, 5, 6, 8, 9. Аналогично выделяется класс B1=2, 4, 7.

Чтобы вычислить дальнейшие разбиения, применим теорему 2. Для этого построим таблицу переходов автомата, руководствуясь правилом: если δ (s, x) принадлежит некому классу, то пишем в соответствующей ячейке имя этого класса. Например, δ 1, a=3∈ A1, δ 3, b=4∈ B1 и так далее.

Выделяя различные комбинации состояний (не выходов!), получим очередное разбиение:

– π 2=1, 5, 6, 3, 9, 8, 2, 4, 7.

Обозначим для удобства A2=1, 5, 6, C2=3, 9, D2=8, B2=2, 4, 7 и построим новую таблицу переходов, используя полученные классы эквивалентности:

Таким образом, получим:

– π 3=1, 5, 6, 3, 9, 8, 2, 4, 7.

– π 4=1, 5, 6, 3, 9, 8, 2, 4, 7.

Так как π 3=π 4, на основании теоремы 3 заключаем, что алгоритм минимизации завершён. Новый минимальный автомат будет включать пять состояний (выполните графическое построение исходного и минимизированного автомата самостоятельно).

Вопросы и упражнения.

1. Минимизировать конечный автомат.

2. Минимизировать конечный автомат.

3. Разработать алгоритм минимизации не полностью определённого конечного автомата, то есть такого, у которого некоторые переходы и выходы не определены (считая, что значения функций переходов и выходов на соответствующих парах аргументов являются безразличными).