Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[28]

v(sj,x) = v(Sj,x) \/x eX . При этом пишут st Ej sj или (Si,Sj) gG(Ei).

В том случае, если sh Sj неэквивалентны, записывают st Er Sj либо Si E sj, либо Si Ej Sj и соответственно (sb Sj) e G( Er), (sit Sj) e G( E), (st, sj) e G(E}) и т.д.

Очевидно, что здесь и в общем случае отношение эквивалентности и неэквивалентности образуют при :

-объединении все множество S*S, т.е. G(Er){jG( Er)=S*S;

-пересечении нулевое множество, т.е. G(Er) f] G( Er) = 0;

-взаимно дополняют друг друга до множества S*S, т.е. G( Ёг) = S*S \ G(Er).

Для примера рассмотрим эквивалентные и неэквивалентные состояния, их графики и первое разбиение на классы эквивалентности для автомата, заданного общей таблицей переходов-таблица 3.8

Таблица 3-8

Общая таблица переходов

x(h)

0

1

s(h)

y/(h+l)/v(h)

so

s2/0

s,/l

Sl

so/1

s2/0

s2

so/2

Si/1

Для указанного автомата имеем :

X = Y={0,1} , S = {s0,Sj,s2j .

Из таблицы 3.8 видно, что состояния s0 и s2 1-эквивалентны, т.к.

v(s0,0)=v(s2,0) = 0]

v(s0,l)=v(s2,l) = l J При этом график 1-эквивалентности имеет вид

G(E1) = {(s0,s2),(s2,s0),(s0,s0),(s1,s1),(s2,s2)} ,

а график 1 -неэквивалентности найдется как

G(E1) = {(s0,s1),(sI,s0),(s1,s2),(s2,sI)} ,

и в него войдут все пары состояний, не попавшие в G(E1) [4].


3.12. МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ

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

Задача минимизации количества состояний в полностью описанном автомате сводится к определению попарно эквивалентных состояний и последующему их объединению. Так, для автомата, заданного таблицей переходов (см. таблицу 3.8), состояния s0 и s2 являются эквивалентными и объединяются в одно, например s0 ,при этом общая таблица переходов принимает вид табл.3.9, а исходный граф автомата, изображенный на рис.3.12, преобразуется к виду, показанному на рис.3.13.

Таблица 3.9

Общая таблица переходов

x(h)

0

1

s(h)

y/(h+l)/v(h)

so

so/0

Si/1

Si

so/1

so/0

Рис.3.12. Граф исходного автоматаРис.3.13. Граф

эквивалентного автомата


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

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

G(E) = fS*S)\G(E) .

Здесь приобретают важное значение следующие теоремы: Теорема 1. Состояние si, и sj, эквивалентные относительно всех входных слов длины г-7, могут стать неэквивалентными относительно

слов длины г только тогда, когда имеется символ хк, где k<r, переводящий sh Sj соответственно в состояния se, sm, не эквивалентные относительно некоторого входного слова длины г-1. Это означает, что на г - м шаге достаточно исследовать состояние в г-1 графике эквивалентности G(Er.i) и установить, найдется ли там пара состояний (su Sj), переходящая в пару (se, s,,) со свойством se Er.i sm. В этом случае sh sj не эквивалентны (st Er Sj). Таким образом, условие теоремы можно записать следующим образом:

SjEjSj, Vxr j еХ (y/(sitxK), y/(Sj,xK)) = (se,sm), хк eX,k<r, seEr jSm\

s.E.s, . (3.14)

r j

Теорема 2. Множество неэквивалентных пар состояний G( Ег) состоит из множества неэквивалентных пар G( Ег.}) и таких пар (suSj), что для некоторого символа хг входного слова длиной г имеем v(si, xr)*v(Sj, xr), т.е.

v(st,хг)фу(Sj,xr), xr eX,=> stErSj G(Er) = G(Er ])[jsiErsJ.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31]