[Список тем]

Минимизация КА

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

Определение 7
Два состояния р и q конечного автомата А = <S, X, Y, S0, , > называются эквивалентными (обозначается pq), если ( X*)*(p, ) = *(q, ).

Для автомата (рис. 8, а) состояния q0 и q2 эквивалентны: любая входная цепочка, поданная на автомат, находящийся в состоянии q0, даст такую же реакцию, как и в случае, когда автомат вначале находился в состоянии q2. Эквивалентные состояния можно объединить в один класс и построить новый автомат, состояниями которого являются классы эквивалентных состояний (см. рис. 8, а). Эквивалентные состояния объединены в классы, эти классы и являются состояниями нового автомата (рис. 8, б). Если мы можем определить на множестве состояний автомата "максимально возможное" разбиение на классы эквивалентности, то, выбирая его классы эквивалентности как новые состояния, получим минимальный автомат, эквивалентный исходному.

Рис. 8. Классы эквивалентных состояний произведения конечных автоматов примера 2

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

Алгоритм состоит в последовательном построении на множестве состояний автомата А разбиений ₀, ₁, ..., таких, что в один класс разбиения _k попадают k-эквивалентные состояния, то есть те, которые неразличимы входными цепочками длиной _k. Такие состояния будем считать находящимися в отношении эквивалентности "i,. Если (p_k q), то р и q назовем k-различимыми. Из определения 7: р _k
q ( X*, | | k)*(p, ) = *(q, ).
Очевидно, что в любом автомате все состояния 0-эквивалентны, поскольку при подаче пустой цепочки на вход автомата (цепочки длины 0) выходом является также пустая цепочка независимо от состояния, в котором автомат находится. Следующее разбиение ₁ также легко построить. Действительно, по определению в один блок ₁ попадают все состояния, в которых автомат одинаково реагирует на входные сигналы:
p ₁ q ( X) (p, x) = (q, x). Разбиения ₀, содержащее один единственный блок, в который входят все состояния автомата, и ₁ каждом блоке которого собраны состояния, не различимые входными сигналами, являются исходными при построении цепочки разбиений ₀, ₁, ..., . Если мы сможем определить, как строить следующее разбиение из предыдущего, то начиная с ₁ мы сможем последовательно построить и всю цепочку.

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

Легко понять справедливость этой теоремы. Действительно, для того чтобы входная цепочка длины k+1, например цепочка X₀X₁X₂...X_k, не различала пару состояний р и q, нужно всего лишь, чтобы автомат из этих состояний переходил под воздействием х₀ в такие состояния, которые не различимы цепочкой X₁X₂...X_k, то есть чтобы (р, х₀) и (q, X₀) были бы k-неразличимы (см. рисунок).

Цепочка длиной k+1

Докажем теорему формально.

(Необходимость.) Нужно доказать p_k+1 q ( x X) (p, x) _k (q, x). Докажем контрапозицию: ( х ( Х)[( ((р, х) ( _k ( (q, х)] ( р _k+1 q. Если состояния (р, х) и (q, х), в которые попадает автомат из р и q под воздействием х, R-различимы, то пусть X₁X₂...x_k - цепочка входных сигналов, их различающая. Тогда, очевидно, цепочка XX₁X₂...Х_k длиной k+1 различает р и q.

(Достаточность.) Нужно доказать (x X)(p, x)_k (q, x) p_k+1 q, ecли p_k q при k > 1. Из определения расширенной функции переходов

*(р, х) = (р, х)*((р, х)а) и *(q, х) = (q, x) *((q, х)).

Поскольку k > 1 и р _kq, ,(р, х) = (q, х). Из того, что (р, х) и (q, х) k-эквивалентны, следует, что ( X^k)*((p, x)) = *((q,x)). Следовательно, для любых цепочек длины k+1, (p, ) = (q, ), то есть p _k+1 q, что и требовалось доказать.

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

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

Доказательство. Из доказанного выше следует, что:

(p, q S)p_k+1 q p_k q & (x X)(p, x)=_k (q,x).

Обозначим R(p, q, k) (x X)(p,x)_k (q, х). Тогда доказанное утверждение теоремы 3.2 запишется:

(p, q S)p_k+1 q p_k q & R(p, q, k).

Пусть теперь p_r+1 q = p_rq. Тогда (p, q S)p _r qp=_r q&R(p, q, k). Но это значит, что

(p, q S)p_r qR(p, q, г).

Предположим теперь, что для некоторого i > r _i = _r, но _{i+1 i}. Это значит, что

[(p, q S)p _i q R(p, q, i)]. Однако, поскольку _i = _r, a R зависит только от _i, это противоречит утверждению (p, q S)p_r q R(p, q, r). и, следовательно, наше предположение неверно, что и требовалось доказать.

Пример 3. Минимизация конечного автомата, заданного таблицей переходов табл. 3, проводится последовательным построением разбиений ₀, ₁, ... .

Таблица 3

Начальное разбиение представляет собой один блок, включающий все состояния, поскольку входные цепочки длиной 0 (пустая цепочка ) не различают состояний: независимо от того, в каком состоянии автомат находился при подаче входа , выходом тоже будет . Поэтому

₀={А₀ = <1,2,3,4,5,6,7,8,9>}.

Разбиение ₁ в один блок объединяет те состояния, которые нельзя различить при подаче цепочек длиной 1. Функция выходов при подаче а и b не может различить 1,3, 5, 6,8 и 9, поскольку для каждого из этих состояний при подаче на вход автомата а он выдает 1, а при подаче на вход b он выдает 0. Состояния 2,4 и 7 попадают в другой блок, но между собой входной цепочкой длины 1 их различить нельзя.
Поэтому:

₁ = (А₁ = <1,3, 5,6,8,9 >; B₁ = <2,4,7>}.

Следующее разбиение ₂ объединяет в один блок те состояния, которые нельзя различить при подаче цепочек длиной 2. Перебирать все такие цепочки долго, поэтому воспользуемся теоремой 2. В соответствии с ней, в один блок разбиения _k+i попадут те состояния р и q, для которых справедливо
(x X)(p, x)_k (q, x). Как было установлено выше, эти состояния должны быть из одного блока предыдущего разбиения. Обратимся к построению ₂.
Построим таблицу переходов, но вместо значения состояния (р, х) будем писать номер блока разбиения ₁ в которое попадает (р, х). Так, (3, а) = 1, а это состояние находится в блоке А₁
Аналогично, (3, b) = 4, а это состояние находится в блоке B₁.
После такого построения видно, что состояния 1,3,5,6,8 и 9 нужно разбить на три элока: <1, 5, 6>, <3, 9> и <8>.
Состояния 2, 4 и 7 попадают в одни и те же блоки предыдущего разбиения ₁ поэтому они попадут в один и тот же блок разбиения ₂.
Итак:

₂ = {А2 = <1,5,6>; В₂ = <2,4,7> С₂ = <3,9>; D₂ = <8>}.
Аналогично строится ₃. При его построении не нужно проверять, в какой блок ₂ будет переводить автомат из состояния 8, поскольку оно единственное в блоке разбиения ₂, и поэтому далее дробиться этот блок не будет. Таким образом,

₃ = {А₃ = <1, 5, 6> В₃ = <2>; С₃ =<4, 7> D₃ = <3, 9> Е₃ = <8>}.

Разбиение ₄ совпадает с разбиением ₃. На основании теоремы 3 искомое разбиение , совпадает с ₃.
Итак, минимальный автомат с эквивалентным поведением имеет 5 состояний, представляющих блоки разбиения ₃, а его функции переводов и выходов определяются так:

(А₃, а) = D₃,
(А₃, b) = А₃,
(А₃, а) = 1 и т. д.

Тест № 1: Представления конечных автоматов (F-схем)

[Список тем]