12. Схемы из функциональных элементов с элементами задержки (СФЭз), автоматность осуществляемых ими отображений. Реализация КАВ СФЭз (Лекции), страница 2

. qikβ = bi1 bi2 . . . bik = ϕ̄(α, q) ∈ B ∗qik+1 = ψ̄(α, q)СФЭЗУпрощение КАВЭксперименты для КАВЭкспериментом для КАВ A = (A, B, Q, ϕ, ψ, q1 ) называетсяпроизвольное слово α ∈ A∗ .Длиной эксперимента α ∈ A∗ называется число символов внем |α|.Эксперимент α ∈ A∗ отличает состояния q 0 ∈ Q и q 00 ∈ Q, еслиϕ̄(α, q 0 ) 6= ϕ̄(α, q 00 ).Иначе, эксперимент α ∈ A∗ не отличает состояния q 0 ∈ Q иq 00 ∈ Q.СФЭЗУпрощение КАВОтличимые и неотличимые состояния КАВПусть A = (A, B, Q, ϕ, ψ, q1 ) – КАВ.Состояния q 0 ∈ Q и q 00 ∈ Q называются отличимыми, еслинайдется эксперимент α ∈ A∗ , который их отличает, т.е.ϕ̄(α, q 0 ) 6= ϕ̄(α, q 00 ).Иначе, состояния q 0 ∈ Q и q 00 ∈ Q называютсянеотличимыми, или эквивалентными.СФЭЗУпрощение КАВПримерПример 1. Пусть A = B = {0, 1}.

Рассмотрим автоматнуюфункцию f : A∞ → B ∞ , задаваемую следующей диаграммойМура.'$ 0(0):∗0(0) q2'$&%6q10(1)1(1)'$?XXX&%XXX1(1)qXXz 31(1)&%Состояния q1 и q2 неотличимы.СФЭЗУпрощение КАВЛемма об отличимых состоянияхЛемма 3. Пусть A = (A, B, Q, ϕ, ψ) – КАВ.Пусть состояния q 0 ∈ Q и q 00 ∈ Q отличимы экспериментомα = ai1 . . .

aik ∈ A∗ длины k и не отличимы никакимэкспериментом меньшей длины.Тогда для каждого l, 1 ≤ l ≤ k, найдутся состояния ql0 ∈ Q иql00 ∈ Q, которые отличимы экспериментом длины l и неотличимы никаким экспериментом меньшей длины.СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1ai2...aikСФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1ai2...aikα = ai1 ai2 . .

. aik ∈ A∗СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0ai2...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0q 00ai2...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q 0 bi1q 00 bi1ai2...aikα = ai1 ai2 .

. . aik ∈ A∗СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1ai2q 0 bi10qk−1q 00 bi100qk−1...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0ai2...aikα = ai1 ai2 . . . aik ∈ A∗000qk−16= qk−1bi10qk−1q 00 bi100qk−1СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1ai2bi20qk−1q 00 bi1bi200qk−1...aikα = ai1 ai2 .

. . aik ∈ A∗000qk−16= qk−1СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1ai2...bi200qk−1qk−2q 00 bi1bi20000qk−1qk−2aikα = ai1 ai2 . . . aik ∈ A∗000qk−16= qk−1СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1ai2...bi200qk−1qk−2q 00 bi1bi20000qk−1qk−2aikα = ai1 ai2 . . . aik ∈ A∗000qk−16 qk−1=000qk−26 qk−2=СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1q 00 bi1ai2...bi2...0qk−10qk−2...bi2...0000qk−1qk−2...aikα = ai1 ai2 . .

. aik ∈ A∗000qk−16 qk−1=000qk−26 qk−2=...СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1q 00 bi1ai2...bi2...0qk−10qk−2...bi2...0000qk−1qk−2...aikq10q100α = ai1 ai2 . . . aik ∈ A∗000qk−16 qk−1=000qk−26 qk−2=...СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1q 00 bi1ai2...bi2...0qk−10qk−2...bi2...0000qk−1qk−2...aikq10q100α = ai1 ai2 .

. . aik ∈ A∗000qk−16= qk−1000qk−26= qk−2...q10 6= q100СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1q 00 bi1ai2...bi2...0qk−10qk−2bi2...aikb...0000qk−1qk−2...q10cq100α = ai1 ai2 . . . aik ∈ A∗000qk−16= qk−1000qk−26= qk−2...q10 6= q100СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1q 00 bi1ai2...bi2...0qk−10qk−2bi2...aikb...0000qk−1qk−2...q10cq100α = ai1 ai2 . .

. aik ∈ A∗000qk−16= qk−1000qk−26= qk−2...q10 6= q100b 6= cСФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство.Входная лентаai1q0bi1q 00 bi1ai2...bi2...0qk−10qk−2bi2...aikb...0000qk−1qk−2...q10cq100α = ai1 ai2 . . . aik ∈ A∗000qk−16= qk−1000qk−26= qk−2...q10 6= q100b 6= cql0 и ql00 – искомыеСФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство. Пусть A = (A, B, Q, ϕ, ψ, q1 ) – КАВ.Пусть состояния q 0 ∈ Q и q 00 ∈ Q отличимы экспериментомα = ai1 . . .

aik ∈ A∗ длины k и не отличимы никакимэкспериментом меньшей длины.Положим для каждого l, 1 ≤ l ≤ k,ql0 = ψ̄(ai1 . . . aik−l , q 0 ) ∈ Q;ql00 = ψ̄(ai1 . . . aik−l , q 00 ) ∈ Q;Тогда1. Состояния ql0 и ql00 отличимы экспериментомαl = aik−l+1 . . . aik длины l.СФЭЗУпрощение КАВЛемма об отличимых состоянияхДоказательство (продолжение). 2. Докажем от противного,что состояния ql0 и ql00 не отличимы никаким экспериментомменьшей длины.Пусть найдется эксперимент α0 ∈ A∗ длины m < l,отличающий состояния ql0 и ql00 .Но тогда состояния q 0 и q 00 отличаются экспериментомα1 = ai1 . .

. aik−l α0 длины (k − l) + m < k.Получаем противоречие с условием.Следовательно, состояния ql0 и ql00 не отличимы никакимэкспериментом длины, меньшей l.СФЭЗУпрощение КАВТеорема МураТеорема 4 (Мура). Пусть A = (A, B, Q, ϕ, ψ, q1 ) – КАВ с rсостояниями (|Q| = r ).Если состояния q 0 ∈ Q и q 00 ∈ Q отличимы, то они отличимыэкспериментом длины, не большей r − 1.Доказательство. Для каждого l, l = 0, 1, . .

. , рассмотримбинарное отношение Rl ⊆ Q × Q на множестве Q:если qi , qj ∈ Q, то qi Rl qj , если они не отличимы никакимэкспериментом длины, меньшей или равной l.Будем полагать, что qi R0 qj для всех qi , qj ∈ Q.СФЭЗУпрощение КАВТеорема МураДоказательство (продолжение). Докажем, что для каждого l,l = 0, 1, .

. . , отношение Rl ⊆ Q × Q является отношениемэквивалентности на множестве Q.1. Рефлексивность: qRl q для кажого состояния q ∈ Q.2. Симметричность: если qi Rl qj , то qj Rl qi .3. Транзитивность: пусть qi Rl qj и qj Rl qs , то есть для каждоготакого эксперимента α ∈ A∗ , что |α| ≤ l, верноϕ̄(α, qi ) = ϕ̄(α, qj );ϕ̄(α, qj ) = ϕ̄(α, qs ).Отсюда верно ϕ̄(α, qi ) = ϕ̄(α, qs ), или qi Rl qs .Следовательно, Rl – отношение эквивалентности на Q.СФЭЗУпрощение КАВТеорема МураДоказательство. Пусть rl = |Q/Rl | – число классовэквивалентности по отношению Rl на множестве Q.

Заметим,что r0 = 1.По условию состояния q 0 ∈ Q и q 00 ∈ Q – отличимы.Пусть α ∈ A∗ – эксперимент минимальной длины,отличающий состояния q 0 ∈ Q и q 00 ∈ Q. Пусть |α| = k.То есть состояния q 0 ∈ Q и q 00 ∈ Q отличимы экспериментомдлины k и не отличимы никаким экспериментом меньшейдлины.Тогда по доказанной лемме для каждого l, 1 ≤ l ≤ k, найдутсясостояния ql0 ∈ Q и ql00 ∈ Q, которые отличимы экспериментомдлины l и не отличимы никаким экспериментом меньшейдлины.СФЭЗУпрощение КАВТеорема МураДоказательство (продолжение). Посмотрим, как устроеныфактор-множества Q/Rl и Q/Rl+1 , и как соотносятся междусобой числа rl и rl+1 .Заметим, что если qi R̄l qj , то qi R̄l+1 qj .То есть если состояния qi и qj отличимы экспериментомдлины, не большей l, то состояния qi и qj отличимы иэкспериментом длины, не большей (l + 1).Поэтому rl ≤ rl+1 .СФЭЗУпрощение КАВТеорема МураДоказательство (продолжение).

Рассмотрим состояния000ql+1∈ Q и ql+1∈ Q. Они не отличимы никаким экспериментомдлины, меньшей (l + 1). Значит, по отношению Rl онинаходятся в одном классе эквивалентности.Но они отличимы экспериментом длины (l + 1). Значит, поотношению Rl+1 они находятся в разных классахэквивалентности.Следовательно, при переходе от фактор-множества Q/Rl кфактор-множеству Q/Rl+1 хотя бы один класс эквивалентностипо отношению Q/Rl разбивается хотя бы на два классаэквивалентности по отношению Rl+1 .Отсюда rl < rl+1 .СФЭЗУпрощение КАВТеорема МураДоказательство (продолжение).

Заметим, что так как|Q| = r , для всех l верно rl ≤ r (в каждом классеэквивалентности не менее одного состояния).Получаем возрастающую последовательности чисел1 = r0 < r1 < r2 < · · · < rk ≤ r .Отсюда k ≤ r − 1.СФЭЗУпрощение КАВПримерыПример 2. Рассмотрим диаграмму Мура автоматной функцииf:∗'$0(0) : q20(0) '$&%6yXXXq10(0)1(1)1(0) XXXX '$X?XXX&%XXXqXXz 31(0)&%Состояния q1 и q2 отличаются экспериментом α = 1.Состояния q2 и q3 также отличаются экспериментом α = 1.Состояния q1 и q3 не отличаются никаким экспериментомдлины, не большей 2. По теореме Мура они неотличимы.СФЭЗУпрощение КАВПримерыДиаграмму Мура функции f можно упростить, отождествивнеотличимые состояния q1 и q3 :∗0(0)'$1(0)q1 , q3'$0(0) q2&%1(1)&%СФЭЗУпрощение КАВПримерыДиаграмму Мура функции f можно упростить, отождествивнеотличимые состояния q1 и q3 :∗0(0)'$1(0)q1 , q3 0 &%1(1)'$0(0) q21&%СФЭЗУпрощение КАВПримерыДиаграмму Мура функции f можно упростить, отождествивнеотличимые состояния q1 и q3 :∗0(0)'$1(0)q1 , q3 0 &%1(1)q(t − 1) x(t) y (t) q(t)0001010010011110'$0(0) q21&%СФЭЗУпрощение КАВПримерыДиаграмму Мура функции f можно упростить, отождествивнеотличимые состояния q1 и q3 :∗0(0)'$1(0)q1 , q3 0 &%1(1)'$0(0) q21&%q(t − 1) x(t) y (t) q(t) 0001 y (t) = x(t) · q(t − 1);q(t) = x̄(t);0100q(0) = 0.10011110СФЭЗУпрощение КАВЗадачи для самостоятельного решения1.

Пусть A = B = {0, 1}. Построить СФЭЗ для автоматногоотображения y (1)y (2) · · · = f (x(1)x(2) . . . ), если1) y (t) = x(t) ∨ y (t − 1) при t ≥ 2, y (1) = 0;2) y (t) – (t + 1)-я цифра после запятой в двоичной записичисла 23 · x(t).2. Построить диаграмму Мура, в которой нет неотличимыхсостояний, для автоматной функции, заданной каноническимиуравнениями:y (t) = x(t) · q1 (t − 1) · q2 (t − 1);q1 (t) = x̄(t);q (t) = x(t) · q1 (t − 1); 2q1 (0) = q2 (0) = 0.СФЭЗУпрощение КАВЛитература к лекции1.

Яблонский С.В. Введение в дискретную математику. М.:Высшая школа, 2001.2. Алексеев В.Б. Лекции по дискретной математике. М.: МАКСПресс, 2004. Стр. 68-74.3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения подискретной математике. М.: Физматлит, 2004.СФЭЗУпрощение КАВКонец лекции.