<<

стр. 2
(всего 2)

СОДЕРЖАНИЕ

k

k




() () k ?1
M 2 k ?1 C2 ? 2 ?
M 2k
? + ?? и
3k ?1
3k 3 ?3?
C2 ? 2 ? 2 ? ? 2? ?
k ?1 k ?2 k ?1 k ?1
2
C ? 2? C ? 2? C ? 2?
f (k ) ? f (k ?1) + 2 ? ? ? f (k ? 2) + 2 ? ? ? ! ? f (1) + ? + ? ? + ! + ? ? ? ? C3
+ 2? ?
? 3? ?
3 ? 3? 3 ? 3? 3 ? 3? 3 ?3 ? 3 ?
? ?
для некоторой константы C3, поскольку сумма в квадратных скобках не превосходит сумму 2
бесконечно убывающей геометрической прогрессии с первым членом 2 и знаменателем 2 .
3 3
( ) ? C и M (2k) ? C 3k. Лемма доказана.
M 2k
Таким образом, 3
3
k
3


Теорема 3. Существует схемный умножитель в базисе {?, &, } с числом элементов
( )
O nlog 2 3 .
Доказательство. Пусть n — любое натуральное число и n>1. Тогда существует нату-
ральное k такое, что 2k–1 < n ? 2k. Для умножения n-разрядных чисел будем использовать схе-
му M 2 k с числом элементов M (2k), подавая на старшие 2k – n разрядов обоих сомножителей 0,
предварительно реализованный подсхемой из 2 элементов. Тогда имеем, исходя из леммы 3
()
M (n ) ? M 2 k + 2 ? C3 3k + 2 = 3C3 3k ?1 + 2 = 3C3 2(k ?1)log 2 3 + 2 < 3C3n log 2 3 + 2 ? Cn log 2 3
для некоторой константы C. Теорема доказана.
Замечание. Существует практически применимый метод Шёнхаге-Штрассена умноже-
ния с оценкой сложности O (n log n · log log n).




27
§25. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка
сложности реализации произвольной функции алгебры логики.
Определение. Дешифратором Qn порядка n называется схема из функциональных эле-
ментов с n входами x1, x2, …, xn и 2n выходами z0 , z1 ,!, z 2n ?1 такая, что если |x1x2…xn| = i, то
?1, x1 ! xn = i
zi = 1 и zj = 0 при i ? j: zi (x1 ,!, xn ) = ? .
0, x1 ! xn ? i
?
Заметим, что если i = (i1, i2, …, in)2, то zi (x1 ,!, xn ) = x1i1 x22 " xnn .
i i


Лемма 4. Существует дешифратор Qn с числом элементов, не превосходящим n2n + 1.
Доказательство. Для реализации каждой zi достаточно взять ровно n–1 конъюнкций и
не более n отрицаний, то есть всего менее, чем 2n функциональных элементов. Всего различ-
ных конъюнкций ровно 2n, и сложность дешифратора не превосходит n2n + 1. Лемма доказана.
Теорема 4. Сложность минимального схемного дешифратора порядка n не меньше, чем
() n
2n и асимптотически не больше, чем 2 n + O n ? 2 2 .
Доказательство. 1) Поскольку у дешифратора Qn ровно 2n выходов, на которых реали-
зуются различные функции, не равные входным переменным, сложность минимального де-
шифратора не меньше, чем 2n.
x1 … xk xk + 1 … xn

? Qn?? k
?
Qk

y?0 y?1 … Q??[l] … y ? n ? k ?1
y0 y1 … Q?[j] … y 2k ?1 2




& &

Qn [1] Qn [i]

2) Докажем существование дешифратора со сложностью 2 + O (n ? 2 ). Разобьём набор
n
n 2



входных переменных x = (x1, …, xn) на поднаборы x? = (x1, …, xk) и x?? = (xk + 1, …, xn), где k —
некоторый параметр и 1 ? k ? n – 1. Пусть Q? и Q?? —функциональные дешифраторы порядка
k и n – k от базовых переменных x? и x??, а ?? и ??? — соответствующие им схемные дешифра-
торы, построенные по лемме. Легко видеть, что любую конъюнкцию Qn [i], 1 ? i ? 2n, можно
представить в виде Qn [i] = Q ?[j]·Q?? [l], где i = 2n – k(j – 1) + l и 1 ? j ? 2k, 1 ? l ? 2n – k. Дешиф-
ратор ? порядка n от базовых переменных x содержит дешифраторы ?? и ??? в качестве под-
схем и реализует каждую функцию алгебры логики Qn [i], 1 ? i ? 2n, с помощью одного
функционального элемента &, входы которого присоединены к выходам ?? и ??? в соответст-
вии с формулой Qn [i] = Q? [j]·Q?? [l]. Из построения ? следует, что L (?) = 2n + L (??) + L (???) ?
()
? 2n + k·2k + 1 + (n – k)2n – k + 1, и поэтому при k = ?n ? получим: L(? ) ? 2 n + O n ? 2 2 . Теорема
n

2
доказана.
Следствие. Для любой функции алгебры логики f(x1,…,xn) существует реализация её
схемой из функциональных элементов в базисе {?,&, } со сложностью, не превосходящей
() n
2 ? 2n + O n ? 2 2 .
Доказательство. Если f ? 0, то реализуем f = x1 ? x1 . Если f ? 0, то
()
f (x1 ,!, xn ) = x1 1 " xn n , и L ? L(Qn ) + 2 n ? 1 ? 2 ? 2n + O n ? 2 2 .
n
?
?
?
(?1 ,!,? n )
f (? )=1
˜


Следствие доказано.

28
§26. Мультиплексор. Верхняя оценка сложности мультиплексора.
Метод Шеннона.

Определение 1. Мультиплексором µn порядка n называется схема из функциональных
элементов с n + 2n входами x1 ,! xn , y0 , y1 ,!, y2n ?1 и 1 выходом z такая, что если на входы
&%$ &# %## # $
адресные входы информационные входы

x1, …, xn поступает набор (?1, …, ?n), то z = y(?1 ,!,? n )2 .
Теорема 5. Существует мультиплексор µn порядка n с числом элементов

()
L(µ n ) ? 3 ? 2 n + O n ? 2 2 .
n




Доказательство. Заметим, что задачу решает функция
? ? ?
z= ? x1 1 ? x2 2 " xn n ? y(?1!? n )2 .
(?1 ,!,? n )

Для её вычисления достаточно использовать один дешифратор, 2n конъюнкций и 2n – 1
дизъюнкций и

()
L(µ n ) ? L(Qn ) + 2 + 2 ? 1 ? 3 ? 2 + O n 2 .
n
n n n 2




Теорема доказана.
x1 … xn y0 y1 … y 2 n ?1

Qn


2n
& & &
"
?

?
2n – 1
'

?


Определение 2. Сложностью L (S) схемы S называется число элементов в ней.
Определение 3. Сложностью функции алгебры логики f (x1, …, xn) называется
L( f ) = min L(S ) .
S реализует f

Определение 4. Функцией Шеннона L(n) для схемы из функциональных элементов на-
зывается L(n ) = max L( f ) .
f от x1 ,!, xn

Обозначения: g (n) ?h (n) ? g (n) ? h (n)·(1 +o(1)); g (n) ? h (n) ? g (n) ? h (n)·(1 +o(1)).
Определение 5. Универсальным многополюсником Un порядка n называется схема из
n n
функциональных элементов с n входами и 2 2 выходами, на которых реализуются все 22
функций от x1, …, xn.




29
Теорема 6 [Ложкин С. А.]. Минимальная сложность универсального многополюсника
n
порядка n равна 2 2 ? n .
Доказательство. 1) Очевидно, что L(U n ) ? 2 2 ? n , так как всего функций алгебры логи-
n



n
ки от n переменных, отличных от входных переменных, ровно 2 2 ? n .
2) Докажем существование универсального многополюсника с числом элементов
n
2 2 ? n . Для этого построим какую-нибудь схему из функциональных элементов, реализую-
щую все функции алгебры логики. Затем оставим из каждой группы эквивалентных вершин
(в которых реализуются одинаковые функции) лишь одну, наиболее близкую к входам, под-
соединив выходы удалённых к выходу оставшейся. В результате получим, что в каждой
вершине реализуется уникальная функция алгебры логики. Но всего функций, отличных от
n n
входных переменных — 2 2 ? n . Следовательно, и вершин — 2 2 ? n . Теорема доказана.
1
Теорема 7. L(n ) ? 6 ? 2 n ? .
n
Доказательство. Рассмотрим произвольную функцию f (x1, …, xn). Выберем некоторое
натуральное k (1 ? k ? n) и рассмотрим разложение взятой функции по первым k переменным:
f (x1 ,!, xn ) = x1 1 ? x2 2 " xk k ? f (? 1 ,!, ? k , xk +1 ,!, xn ) .
? ? ?
?
(?1 ,!,? k )

Построим схему из функциональных элементов из универсального многополюсника Un–k по-
рядка n – k от базовых переменных xk + 1, …, xn и мультиплексора µn порядка n с адресными
переменными x1, …, xk, на информационные входы которого подаются выходы Un – k. Муль-
()
k
типлексор можно построить так, что его сложность не превзойдёт 3 ? 2k + O k ? 2 2 , а универ-
n? k
сальный многополюсник так, что его сложность будет не больше, чем 2 2 . Итак,
()
L(n ) = L(µ n ) + L(U n?k ) ? 3 ? 2 + O k ? 2 + 2 2 . Следовательно, полагая
k n?k
k 2




k = ?n ? log 2 (n ? 2 log 2 n )? (при этом k ? n – log2(n – 2log2n) + 1, а n – k ? log2(n – 2log2n)),

? 2n ?
2 n 2n ? k 2n
1
n ?log 2 (n ? 2 log 2 n )+1
= 2 = o? ? и в
n ? 2 log 2 n
n +1
получим, что 2 ? 2 =2 ? ˜ 2? , 2 ? 2
k
?n?
n ? 2 log 2 n n n ??
итоге
? ? n ? ? 2 n ??
2n 2n
L(S ) ? ?3 ? 2 ? + O? n 2 ? + o? ?? ˜ 6 ? .
2?
??
?
n ? ? n ?? n
? ?
? ?
Теорема доказана.
Определение 6. Пусть ? (L, n) — число всех попарно неизоморфных схем из функцио-
нальных элементов с входными переменными x1, …, xn и выходной переменной z1, слож-
ность которых не превосходит L.
Лемма 5. В функциональном базисе {&, ?, } ? (L, n) ? (L + n)2L + 4.
Доказательство. Можно выбрать целые неотрицательные числа L1, L2, L3 так, чтобы их
сумма не превосходила L, не более, чем (L + 1)3 способами. Можно взять L1 конъюнкций, L2
дизъюнкций, L3 отрицаний, а затем каждый вход каждого из них «присоединить» к выходу
некоторого другого функционального элемента или к входу схемы не более, чем (L + n)2L
способами, и пометить в качестве выхода одну из не более, чем L + n точек.
Тогда ? (L, n) ? (L + 1)3·(L + n)2L·(L + n) ? (L + n)2L + 4. Лемма доказана.




30
1 2n
Теорема 8. Для функции Шеннона L (n) справедливо L(n ) ? ? .
2n
Доказательство. Очевидно, ? (L(n ), n ) ? 2 2 , но в то же время согласно лемме ? (L, n) ?
n




(L(n ) + n )2 L (n )+4 ? 2 2 ? (2 L(n ) + 4 )log 2 (L(n ) + n ) ? 2 n . Так как
n
? (L + n)2L+4. Следовательно,
2n
L(n )? 6 ? 2 ? ,то начиная с некоторого номера n, n + L (n) ? 2 и 2 L(n ) + 4 ? n
n
, откуда
1
n
n
1 2n
L(n )? ? . Теорема доказана.
2n

§27. Шифратор. Верхняя оценка сложности шифратора.
Определение. Шифратором Dn порядка n называется схема из функциональных эле-
ментов с 2n входами x0 , x1 , !, x2n ?1 и n выходами y1,y2,…,yn такая, что если на вход поступает
набор с одной единицей по переменной xi, то на выходе образуется набор (?1, ?2, …, ?n)2 = i.
Теорема 9. Существует шифратор Dn порядка n со сложностью, не превосходящей
n·2n – 1.
Доказательство. Задачу решает система функций
yj = ? x
(?1 ,!,? j ?1 ,1,? j +1 ,!,? n ) (?1 ,!,? j ?1 ,1,? j +1 ,!,? n )

(например, yn = x1 ? x3 ? x5 ? x7 ? ! ? x2n ?1 ). Всего в каждой дизъюнкции 2n – 1 слагаемых, сле-
довательно, необходимо 2n – 1 – 1 дизъюнкторов, всего таких функций надо реализовать n, то
есть получаем оценку сложности шифратора L (Dn) ? (2n – 1 – 1) · n < n · 2n – 1. Теорема
доказана.




31
Глава IV. Основы теории кодирования
§28. Алфавитное кодирование.
Теорема Маркова о взаимной однозначности алфавитного кодирования.
Определение 1. Пусть A = {a1, a2, …, ar} — исходный алфавит, B = {b1, b2, …, bm} —
кодирующий алфавит и
A* = ? ? A ? A2 ? A3 ? … ? An ? …, B* = ? ? B ? B2 ? B3 ? … ? Bn ? ….
Тогда алфавитным кодированием A* > B* назовём отображение ? : A > B* такое, что ai > Bi.
Множество {B1, B2, …, Br} при этом называется множеством кодовых слов (или просто ко-
дом). При этом ? : ai1 ai2 ! ais > Bi1 Bi2 ! Bis .
Определение 2. Кодирование A* > B* называется взаимно однозначным (декодируемым,
() ()
разделимым), если для любых слов a1 ? A? и a2 ? A? a1 ? a2 ? ? a1 ? ? a2 .
Определение 3. Код называется равномерным, если длины всех его кодовых слов
одинаковы.
Утверждение 1. Любой равномерный код является взаимно однозначным.
Определение 4. Код называется префиксным, если никакое кодовое слово не является
началом другого.
Утверждение 2. Любое префиксное кодирование является взаимно однозначным.
Определение 5. Код называется постфиксным (суффиксным), если никакое кодовое
слово не является концом другого.
Утверждение 3. Любое постфиксное кодирование является взаимно однозначным.
Определение 6. Слово b ? B ? называется неприводимым, если b декодируется неодно-
значно, однако, при выбрасывании из b любого связного непустого куска получается слово,
которое декодируется не более, чем одним способом.
Теорема 1 [Марков А. А.]. Пусть ?: ai > Bi (i = 1, 2, …, r) — некоторое кодирование.
Пусть W — максимальное число кодовых слов, которые «помещаются» подряд внутри кодо-
r
вого слова. Пусть li — длина слова Bi и L = ? li . Тогда если кодирование ? не взаимно одно-
i =1

значно, то существуют два различных слова a' ? A*, a'' ? A*,
длина(a?) ? ?(W +1)(2L?r +2 ) ? , длина(a??) ? ?(W +1)(2L?r + 2 ) ? и ? (a') = ? (a'').
Доказательство. Пусть ? не является взаимно однозначным. Тогда существует некото-
рое слово b1 , которое допускает две расшифровки. Если слово b1 не является неприводи-
мым, то выбрасывая из b1 куски несколько раз, получим неприводимое слово b ; иначе, по-
ложим b = b1 . Очевидно, это всегда можно сделать. Рассмотрим любые две декодировки
слова b . Разрежем слово b в концевых точках кодовых слов каждого из разбиений. Слова
нового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементар-
ными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами ко-
довых слов одного разбиения и концами слов второго разбиения).




Лемма. Если b — неприводимое слово, то все слова ?1, ?2, …, ?m II класса различны.
Доказательство. Пусть ?' = ?''. Тогда, очевидно, слово b не будет неприводимым, по-
скольку при выкидывании отрезка между ?' и ?'', вместе с любым из этих слов, получим сно-
ва две различные расшифровки этого слова (проверьте). Лемма доказана.

32
Таким образом, все ?1, ?2, …, ?m разные. Тогда число слов второго класса не превосхо-
дит числа непустых начал элементарных кодов, то есть не превосходит
(l1 – 1) + (l2 – 1) + … + (lr – 1) = L – r.
Слова из второго класса разбивают слово не более чем на L – r + 1 кусков. Рассмотрим пары
соседних кусков. Тогда согласно одному разбиению в одной половинке уложится не более
одного кодового слова, а в другой — не более W (согласно второму разбиению ситуация сим-
метрична). Всего пар кусков не больше, чем
?L ?2r +1 ? ? L ?2r + 2 ,
а в каждом из них укладывается слов не более чем W + 1. Отсюда число кодовых слов в лю-
бом разбиении не превосходит L?2+ 2 (W + 1) , а поскольку число целое, то не превосходит и це-
r


?( ?. Теорема доказана.
W +1)(L ? r + 2 )
лой части 2


§29. Неравенство Макмиллана.

Теорема 2 (неравенство Макмиллана). Пусть задано кодирование ? : ai > Bi
(i = 1, 2, …, r) и пусть в кодирующем алфавите B — q букв и длина (Bi) = li (i = 1, 2, …, r). То-
гда если ? взаимно однозначно, то
r
1
? q li ? 1 .
i =1

r
1
Доказательство. Положим x = ? . Тогда для любого натурального n
q li
i =1


?r 1 ?? r 1 ? ?r 1 ? rr r
? = ?? ! ? l +l 1+!+l .
x = ? ? li ?? ? l ?"? ? l
n
? i =1 q 1 ?? i =1 q i2 ? ? i =1 q in ? i =1 i =1 i =1 q i1 i2 in
?1 ?? 2 ? ?n ?12 n


n ?l max
ck
?
Обозначая lmax = max li , получим, что эта сумма равна .
qk
1?i ? r
k =1
k
Лемма. ck ? q (?k).
Доказательство. За ck обозначено, очевидно, число наборов (i1, …, in) (1 ? ij ? r), для ко-
торых li1 + li2 + ! + lin = k . Но такой сумме соответствует слово Bi1 Bi2 ! Bin и

( )
длина Bi1 Bi2 ! Bin = li1 + li2 + ! + lin = k .
В силу того, что кодирование взаимно однозначно, различным наборам, соответствуют различ-
ные сообщения, а различных сообщений длины k в алфавите из q букв не более qk ? ck ? qk (?k).
Лемма доказана.
nl max
ck nl max
Согласно лемме x = ? k ? ?1 = nlmax ? x ? n nlmax , ?n . Устремляя n к бесконечности,
n

k =1 q k =1

получаем x ? 1. Теорема доказана.

§30. Существование префиксного кода с заданными длинами кодовых слов.
Теорема 3. Если |B| = q и натуральные числа l1, l2, …, lr удовлетворяют неравенству
r
1
? q li ? 1 ,
i =1
то существует префиксный код B1, B2, …, Br (в алфавите B) такой, что
длина(Bi) = li (i = 1, 2, …, r).

33
r
1
?q ? 1 и для любого k существует ровно dk таких i, что li = k,
Доказательство. Пусть li
i =1
l max
dk
?q ? 1 . Тогда надо построить префиксный код, в котором ровно d1 слов длины 1, d2
то есть k
k =1
m
dk
?q
слов длины 2, и т. д., dl max слов длины lmax. Имеем ?m (1 ? m ? lmax) ? 1 , или, что то же
k
k =1
самое,

( )
d1 d 2 d d
+ 2 + ! + m?1 + m ? 1 ? d m ? q m ? d1q m?1 + d 2 q m?2 + ! + d m?1q .
q m?1 q m
qq
Рассмотрим это неравенство для m = 1: d1 ? q. Для слов длины 1 всего предоставляется воз-
можностей в алфавите мощности q — ровно q вариантов. После выбора d1 слов длины 1 рас-
смотрим неравенство для m = 2: d2 ? q2 – d1q. Всего слов длины 2 — q2, однако все они могут
начинаться лишь с тех букв, которые не были выбраны в качестве слов длины 1, следова-
тельно, остаётся ровно q2 – d1q возможностей выбрать слова длины 2, что удовлетворяет ус-
ловию d2 ? q2 – d1q. Пусть уже выбраны d1 слов длины 1, d2 слов длины 2, и т. д., dm – 1 слов
длины m – 1. Тогда для слов длины m разрешено возможностей не меньше, чем
qm – dm – 1q – dm – 2q2 – … – d2qm – 2 – d1qm – 1,
что удовлетворяет условию. Теорема доказана.
Следствие. Если существует взаимно однозначное кодирование со спектром длин слов
l1, l2, …, lr в алфавите B, то в B существует префиксный код с тем же спектром длин слов.

§31. Оптимальные коды, их свойства.

Будем рассматривать кодирование A* > {0, 1}*. Пусть известны некоторые частоты p1,
p2, …, pk появления символов кодируемого алфавита в тексте:
p1 ? a1 > B1 ? l1
p2 ? a2 > B2 ? l2
, lj — длина j-го кодового слова, p1 + p2 + … + pk = 1, pj > 0.
( ( ((
pk ? ak > Bk ? lk
Определение 1. Ценой (стоимостью, избыточностью) кодирования ? называется
k
функция c(? ) = ? pili . При кодировании текста длины N его длина становится примерно
i =1
равной
k k

? (Np )l = N ? pi li .
i i
i =1 i =1

Определение 2. Взаимно однозначное кодирование ? называется оптимальным, если на
с(? ).
нём достигается inf
? ?взаимно однозначное

Утверждение 4. Если существует оптимальный код, то существует оптимальный пре-
фиксный код с тем же спектром длин слов.
Лемма 1. Если ? — оптимальное кодирование и pi > pj, то li ? lj.
Доказательство. Допустим, что pi > pj и li > lj. Рассмотрим кодирование ? и рассмотрим
? ai > Bi ?ai > B j
, ?? : ?
кодирование ?', в котором переставим кодовые слова Bi и Bj: ? : ? .
a j > Bj a j > Bi
? ?



34
Тогда c (?) – c (?') = (pili + pjlj) – (pilj + pjli) = (pi – pj)(li – lj) > 0 ? c (?') < c (?) ? ? не является
оптимальным — противоречие.
Лемма доказана.
Лемма 2. Если ? — оптимальное префиксное кодирование и lmax = max li , длина(Bj) =
1?i ?k

= lmax, Bj = Bj'?, где ? ? {0, 1}, то в коде ? существует слово Br такое, что Br = B?j? .
Доказательство. Допустим, что в ? нет слова B?j? . Тогда заменим в ? Bj'? на Bj'. Полу-
чим код ?', который является префиксным, но
c(? ) ? c(? ?) = p j дл(B?j? )? p j дл(B?j ) = p j ? c(? ?) < c(? ) ,

следовательно, ? не является оптимальным — противоречие. Лемма доказана.
Лемма 3. Если ? — оптимальное префиксное кодирование и p1 ? p2 ? … ? pk–1 ? pk, то
можно так переставить слова в коде ?, что получится оптимальное префиксное кодирование
? ?
?' такое, что слова Bk ?1 и Bk в нём будут различаться только в последнем разряде.
Доказательство. Пусть p1 ? p2 ? … ? pk–1 ? pk. По лемме 2 в коде ? есть слова B?0 и B?1
максимальной длины. Поменяем их местами с Bk–1 и Bk. Так как pk–1 ? pi и pk ? pi для
1 ? i ? k – 2, то цена кодирования не увеличится и код останется оптимальным (префиксным).
Лемма доказана.
p , p ,!, pk ?1 , p?, p??
p1 , p2 ,!, pk
?: 1 2
Лемма 4. Рассмотрим кодирования ? : и? ,
B1 , B2 ,!, Bk B1 , B2 ,!, Bk ?1 , Bk 0, Bk 1
где p' + p'' = pk. Если один из этих наборов префиксный, то второй также префиксный и
c(?') = c(?) + pk.
Доказательство. Рассмотрим
c(?') – c(?) = p' · дл(Bk0) + p'' · дл(Bk1) – pk · дл(Bk) = p'(lk + 1) + p''(lk + 1) – pklk =
= (p' + p'')lk + (p' + p'') – pklk = pk.
Лемма доказана.

§32. Теорема редукции.
Теорема 4 (теорема редукции). Пусть заданы 2 набора частот и 2 набора слов:
p , p ,!, pk ?1 , p?, p??
p1 , p2 ,!, pk
и ?? : 1 2
?: .
B1 , B2 ,!, Bk B1 , B2 ,!, Bk ?1 , Bk 0, Bk 1
1) Тогда если ?? — оптимальное префиксное кодирование, то и ? — оптимальное пре-
фиксное кодирование.
2) Если же ? — оптимальное префиксное кодирование и p1 ? p2 ? … ? pk–1 ? p? ? p?, то ??
— также оптимальное префиксное кодирование.
Доказательство. 1) Очевидно, из префиксности ?? следует префиксность ?. Допустим,
что ? не оптимально. Тогда существует префиксный код ?1: c(?1) < c(?) для тех же распреде-
p , p , ! , pk
лений частот. Пусть ?1 : 1 2 . Рассмотрим новое кодирование
D1 , D2 ,!, Dk

p1 , p2 ,!, pk ?1 , p?, p??
?
?1 : .
D1 , D2 ,!, Dk ?1 , Dk 0, Dk 1
Очевидно, кодирование ?1? также является префиксным и




35
? c(? ?) = c(? ) + pk
? {c(?1 ) < c(? )} ? c(?1 ) = c(?1 ) + pk < c(? ) + pk = c(? ?).
?
?
c(?1 ) = c(?1 ) + pk
?
?
Следовательно, ?? не является оптимальным кодированием, что противоречит условию. Ос-
таётся предположить, что ? оптимально.
2) Пусть ? — оптимальное префиксное кодирование и p1 ? p2 ? … ? pk–1 ? p? ? p??. Допус-
тим, что ?? не оптимально. Тогда для частот p1, p2, …, pk–1, p?, p?? существует оптимальное
префиксное кодирование ?1?: D1, …, Dk–1, Dk0, Dk1 и c(?1?) < c(?). Тогда для частот
p1, p2, …, pk рассмотрим кодирование ?1: D1, …, Dk–1, Dk. Получим
c(?1) = c(?1?) – pk < c(??) – pk = c(?) ? c(?1) < c(?)
и ? не оптимально, что противоречит условию. Теорема доказана.

§33. Коды с исправлением r ошибок. Оценка функции Mr (n).
Будем рассматривать равномерные коды, длины всех слов, равные n, и ошибки типа за-
мещения, то есть вида 0 > 1 и 1 > 0.
Определение 1. Код называется исправляющим r ошибок, если при наличии в любом
кодовом слове не более r ошибок типа замещения можно восстановить исходное кодовое
слово.
Определение 2. Расстоянием Хэмминга (между 2 наборами длины n) называется число
разрядов, в которых эти наборы различаются.
Определение 3. Шаром (сферой) радиуса r с центром в точке ? = (?1 ,!,? n ) называет-
˜
˜
ся множество всех наборов длины n, расстояние от которых до ? не превосходит r (в точно-
сти равно r).
Определение 4. Кодовым расстоянием называется расстояние по Хэммингу
? (? ,? ) .
˜˜
?= min
min i j
˜˜
? i ,? j из кода, ? i ?? j


Утверждение 1. Код K = {˜1 , ? 2 ,!,? m } исправляет r ошибок тогда и только тогда, когда
?˜ ˜

? min (K ) ? 2r + 1 .
Доказательство. Заметим, что условие утверждения эквивалентно тому, что расстояние
между центрами шаров радиуса r (кодовыми словами) не меньше, чем 2r + 1, что эквива-
лентно тому, что эти шары не пересекаются. Таким образом, на выходе получится слово,
принадлежащее единственному однозначно определённому шару (если в слове не более r
ошибок), что позволяет точно восстановить слово, так как известен центр этого шара. Ут-
верждение доказано.
Определение 5. Код обнаруживает r ошибок, если при наличии в нём не более r оши-
бок типа замещения можно сказать, были ошибки, или их не было.
Утверждение 2. Код K = {˜1 , ? 2 ,!,? m } обнаруживает r ошибок тогда и только тогда,
?˜ ˜
когда
? min (K) ? r + 1.
Доказательство. Условие утверждения эквивалентно тому, что ни один из центров ша-
ров (кодовое слово) не содержится в каком-либо другом шаре, то есть если произошло не бо-
лее r ошибок, можно в точности установить, что полученное на выходе слово не совпадает с
центром одного из шаров. Утверждение доказано.
Определение 6. Функция Mr (n) есть максимальное число слов длины n, образующих код,
исправляющий r ошибок. Sr (n) — число точек (наборов длины n) в шаре радиуса r.



36
?n? ?n? ?n?
Утверждение 3. S r (n ) = 1 + ? ? + ? ? + ! + ? ? .
?1? ? 2? ?r?
???? ??
Доказательство. Точки шара радиуса r — это его центр, множество наборов, отличаю-
?n?
щихся от центра в одной координате — ? ? , множество наборов, отличающихся от центра в
?1?
??
?n?
2 координатах — ? ? , и т. д. Получаем утверждение.
? 2?
??
2n 2n
? M r (n ) ?
Теорема 5. .
S 2 r (n ) S r (n )
Доказательство. Рассмотрим произвольный код K = {˜1 , ? 2 ,!,? m }, исправляющий r
?˜ ˜
ошибок. Из утверждения 1 следует, что шары радиуса r не могут пересекаться, следователь-
но, число всех точек всех шаров не превосходит числа точек n-мерного куба и
2n 2n
m ? S r (n ) ? 2 ? m ? ? M r (n ) ?
n
.
S r (n ) S r (n )
Теперь будем строить код K = {˜1 ,? 2 ,!}. Выберем произвольно точку ?1 . Для выбора
?˜ ˜
˜
точки ? 2 запрещено S2r(n) точек, так как запрещены все точки одного шара и все точки, рас-
положенные от любой граничной точки на расстояние, не больше, чем r, то есть все точки
˜ ˜ ˜
шара радиуса 2r с центром в точке ?1 . Пусть уже выбраны наборы ?1 ,!,? k . Для выбора на-
˜
бора ? k +1 запрещено точек не больше, чем k·S2r (n), то есть, если k·S2r (n) < 2n, то можно вы-
˜
брать ? k +1 . Тупик наступит при выборе m-го набора, когда

2n 2n
m ? S 2 r (n ) ? 2 ? m ? ? M r (n ) ?
n
.
S 2 r (n ) S 2 r (n )
Теорема доказана.

§34. Коды Хэмминга. Оценка функции M1 (n).
Рассмотрим коды, исправляющие одну ошибку типа замещения в словах длины n. Вы-
берем натуральное k таким, что
? k ? log 2 n + 1
? k = ?log 2 n + 1? = ?log 2 (n + 1)? .
2k ?1 ? n ? 2k ? 1 ? ?
k ? log 2 (n + 1)
?
Разобьём номера всех разрядов исходного слова на k классов:
Di = {m | m = (mk–1mk–2…m0)2, mi = 1}, 1 ? m ? n.
так, например, D0 = {1, 3, 5, 7, …}, D1 = {2, 3, 6, 7, …}, D2 = {4, …}.
Определение. Кодом Хэмминга порядка n называется множество наборов
? = (? ,? ,!,? ) ? E k ,
˜
1 2 2
n

удовлетворяющих системе уравнений (суммы по модулю 2):
? ? j?D ? j = 0
? 0


? ? j?D1 ? j = 0
.
?
(
?
?? ? =0
? j?Dk ?1 j


37
Теорема 6. Код Хэмминга порядка n содержит 2n – k наборов, где k = ?log 2 n ? + 1 и ис-
правляет одну ошибку.
Доказательство. Рассмотрим систему уравнений из определения кода Хэмминга
??1 ? (? 3 ? !) = 0
? ? ? (!) = 0
? 2
.
?
(
?
? ? 2k ?1 ? (!) = 0
?
Задаём произвольно ?j, кроме ?1 ,? 2 ,? 4 ,!,? 2k ?1 . Это можно сделать 2n – k способами. Так как
?1 ,? 2 ,? 4 ,!,? 2k ?1 в скобках не встречаются, то они однозначно определяются из системы.
Пусть передано кодовое слово ? = (?1? 2 !? n ) , ошибка произошла в d-ом разряде и
˜
˜
пусть d = (?k–1?k–2…?1?0)2. Пусть на выходе получено слово ? = (?1 ? 2 ! ? n ) , при этом ?i = ?i
? ? ,? ? ? ,!, ? ??
при i ? d, ?d = ?d ? 1. Обозначим ? 0 = = = .
k ?1
j 1 j j
j?D0 j?D1 j?Dk ?1

Утверждение. (?k–1?k–2…?1?0)2 = d.
?? ??
Доказательство. Пусть ?i = 0 ? d ? Di, тогда , следовательно, ?i = 0 и ?i = ?i.
=
j j
j?Di j?Di

? ? = ?? ?1 = 1 ? ? i = 1 ? ? i = ? i .
Пусть теперь ?i = 1 и d ? Di. Тогда i i
j?Di j?Di

Утверждение доказано.
Теорема доказана.
Замечание. Обычно разряды с номерами 1, 2, 4, 8, …, 2k–1 называют проверочными (или
контрольными), остальные — информационными.
2n 2n
? M 1 (n ) ?
Теорема 7. .
n +1
2n
2n 2n
? M r (n ) ?
Доказательство. Имеем . Правое неравенство следует из того,
S 2 r (n ) S r (n )
что S1 (n) = n + 1. Заметим предварительно, что аналогично нельзя получить и левое неравен-
ство, так как
n(n ? 1) n 2
?n?
S 2 (n ) = 1 + n + ? ? = 1 + n + ˜ .
? 2? 2 2
??
Всего различных слов в коде, исправляющем одну ошибку — m = 2n–k. Поскольку
k = ?log 2 n ? + 1 , имеем

2n 2n
? M 1 (n ) ? m ?
n ?log 2 n ?1
k ? log 2 n + 1 ? m ? 2 = .
2n 2n
Теорема доказана.




38
Глава V. Основы теории конечных автоматов
§35. Понятие ограниченно детерминированных (автоматных) функций,
их представление диаграммой Мура. Единичная задержка.
Пусть даны A = {a1, a2, …, ar} — входной алфавит и B = {b1, b2, …, bm} — выходной ал-
фавит. Определим множества A? и B? как множества всевозможных последовательностей в
алфавитах A и B соответственно.
Определение 1. Отображение ?: A? > B? называется детерминированной функцией
(д.-функцией), если b(t) для любого t = 1, 2, … однозначно определяется по a(1), a(2), …, a(t).
a (1)! a1 (t )! > b1 (1)!b1 (t )!
Обозначать д.-функции будем так: ? : 1 , причём,
a2 (1)! a2 (t )! > b2 (1)!b2 (t )!
если a1 (1) = a2 (1), то b1 (1) = b2 (1);
? a1 (1) = a2 (1)
?a (2 ) = a (2)
?1 2
если ? , то b1(t) = b2(t).
(
?
? a1 (t ) = a2 (t )
?
Определение 2. Пусть задана д.-функция ?: A? > B?. Рассмотрим произвольное слово
a = a1a2 ! ak ? A* . Определим функцию ? a следующим образом: пусть a(1), a(2), …, a(t)…
— произвольная входная последовательность. Рассмотрим
? (a1a2…aka(1)a(2)…a(t)…) = b1b2…bkb(1)b(2)…b(t)….
Тогда положим ? a (a (1)a (2)! a(t )!) = b(1)b(2 )!b(t )! . ? a при этом называется остаточной
функцией для ? по слову a ? A? .
Определение 3. Детерминированная функция ? : A?>B? называется ограниченно де-
терминированной, если у неё имеется лишь конечное число различных остаточных функций.
Определение 4. Автоматом (инициальным) называется любая шестёрка
(A, B, Q, G, F, q0), где A, B, Q — конечные алфавиты, G: A ? Q > Q, F: A ? Q > B, q0 ? Q —
начальное состояние.
Входом автомата служит последовательность a(1)a(2)a(3)…, a(t)… ? A* (конечная или
бесконечная), выходом автомата служит последовательность z(t), при этом автомат задаётся
системой канонических уравнений
? z (t ) = F (x(t ), q (t ? 1)),
?
?q (t ) = G (x(t ), q (t ? 1)),
? q (0) = q0 .
?
Определение 5. Отображение ?: A? > B? называется автоматной функцией, если су-
ществует автомат, который реализует это отображение.
Утверждение. Функция является автоматной тогда и только тогда, когда она является
ограниченно детерминированной.
Пример. Пусть A = B = Q = {0, 1} и система канонических уравнений выглядит сле-
дующим образом:
? z (t ) = q(t ? 1),
?
? q(t ) = x(t ),
? q(0) = 0.
?


39
Такой автомат, очевидно, осуществляет отображение a(1)a(2)…>0a(1)a(2)… и называ-
ется единичной задержкой.
x (t) a (1) a (2) a (3)
q (t) 0 a (1) a (2) a (3)
z (t) 0 a(1) a(2)
Определение 6. Диаграммой Мура для автомата называется ориентированный граф с
множеством вершин Q, у которого каждой паре (a, q) сопоставляется дуга, идущая из верши-
ны q в вершину, соответствующую G (a, q). Этой дуге приписывается пометка (a, F (a, q)).
Особым образом помечена вершина, соответствующая начальному состоянию. Диаграмма
Мура однозначно задаёт автомат.

§36. Схемы из функциональных элементов и элементов задержки.
Автоматность осуществляемых ими отображений.
Определение. Схемой из функциональных элементов и элемента задержки называется
схема из функциональных элементов в функциональном базисе, к которому добавлен эле-
мент, реализующий функцию единичной задержки. В схеме из функциональных элементов и
элементов задержки допускаются ориентированные циклы, но любой ориентированный цикл
должен проходить хотя бы через одну задержку.
Пусть A = B = {0, 1}, E2n — множество всех булевых векторов длины n.
Теорема 1. Схема из функциональных элементов и задержки осуществляет автоматное
отображение.
Доказательство. 1) Пусть в схеме имеется r элементов задержки. Пусть i-я задержка Ri
приписана вершине vi, в которую идёт дуга из вершины wi. Для всех i = 1, …, r удалим из
СФЭЗ дуги (wi, vi). По определению СФЭЗ в полученном после этого графе не будет ориен-
тированных циклов и он, тем самым будет представлять собой СФЭ. Входами этой СФЭ бу-
дут все входы исходной схемы, а также все вершины vi, i = 1, …, r (заметим, что все они раз-
личны и отличны от входов исходной схемы). Выходами полученной СФЭ объявим все вы-
ходы исходной схемы и вершины wi, i = 1, …, r. Пусть в исходной схеме выходам приписаны
переменные z1, …, zm, входам — переменные x1, …, xn. Вершинам vi припишем переменные
q'1, …, q'r, а вершинам wi — переменные q1, …, qr. В соответствии с определением функцио-
нирования СФЭ, для некоторых функций алгебры логики fi, gj справедливо:
? zi = f i (x1 ,!, xn , q1 ,!, qr ), i = 1,!, m,
? ?
(1)
?
?q j = g j (x1 ,!, xn , q1 ,!, qr ), j = 1,!, r.
? ?

Естественно считать, что равенства (1) выполняются в каждый момент времени t = 1, 2, 3,…,
то есть
? zi (t ) = f i (x1 (t ),! , xn (t ), q1 (t ),!, qr (t )), i = 1,! m,
? ?
(2)
?
?q j (t ) = g j (x1 (t ), !, xn (t ), q1 (t ),!, q? (t )), j = 1,! , r.
? r


Так как, в соответствии с каноническими уравнениями элемента единичной задержки его
выход в момент t совпадает с его входом в момент t – 1, то естественно считать, что в исход-
ной схеме q'i (t) = qi (t – 1) при t = 1, 2, … для всех i = 1, …, r, где qi (0) = 0. Тогда равенства (2)
принимают вид (где i = 1, …, m и j = 1, …, r):
? zi (t ) = f i (x1 (t ),!, xn (t ), q1 (t ? 1),!, qr (t ? 1)),
?
?q j (t ) = g j (x1 (t ),! , xn (t ), q1 (t ? 1),!, qr (t ? 1)), (3)
? q j (0) = 0.
?
Полученные равенства определяют функционирование СФЭЗ и называются её канонически-
ми уравнениями.

40
2) Пусть отображение ?, осуществляемое схемой ?, задаётся каноническими уравне-
ниями (3). Введём переменные X = (x1, …, xn), Q = (q1, …, qr), Z = (z1, …, zm), принимающие
значения, соответственно в E2n , E2r , E2 . Положим q0 = (0, …, 0). Тогда (3) можно переписать
m


в виде
?Z (t ) = F (X (t ), Q(t ? 1)),
?
?Q(t ) = G (X (t ), Q(t ? 1)),
? Q(0) = q0 ,
?
где функции F, G не зависят явно от t. Отсюда видно, что отображение, осуществляемое схе-
( )
n m r
мой, совпадает с отображением, задаваемым автоматом E2 , E2 , E2 , G, F , q0 , то есть является
автоматной функцией. Теорема доказана.

§37. Моделирование автоматной функции схемой из функциональных элементов
и элементов задержки.

Определение. Пусть автоматная функция ? отображает последовательности в конечном
алфавите A в последовательности в конечном алфавите B. Пусть СФЭЗ ? осуществляет пре-
образование ? последовательностей с элементами из E2 в последовательности с элементами
n


из E2 . Будем говорить, что ? моделирует ?, если существуют отображения (кодирования)
m


K1 : A > E2 и K 2 : B > E2 , сопоставляющие разным элементам разные элементы и обла-
n m


дающие свойством: для любой последовательности P = a(1)a(2)…a(t) в алфавите A, если
? (P) = T = b(1)b(2)…b(t), то ? (K1 (P)) = K2 (T), где K1 (P) = K1 (a(1))K1 (a(2))…K1 (a(t)),
K2 (T) = K2 (b(1))K2 (b(2))…K2 (b(t)).
Теорема 2. Для любой автоматной функции существует моделирующая её СФЭЗ в ба-
зисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элемента
задержки.
Доказательство. Пусть автоматная функция дана автоматом D = (A, B, Q, G, F, q0). Вы-
берем n, m, r так, что 2n ? |A|, 2m ? |B|, 2r ? |Q|. Рассмотрим произвольные отображения (коди-
рования) K1 : A > E2 , K 2 : B > E2 , K 3 : Q > E2r , при которых разные элементы отобража-
n m


ются в разные элементы. Дополнительно потребуем, чтобы K3 (q0) = (0, …, 0). Рассмотрим
отображения G? : E2 ? E2 > E2r и F ? : E2 ? E2 > E2m такие, что для любых a ? A и q ? Q
n r n r


выполняется
?G?(K1 (a ), K 3 (q )) = K 3 (G (a, q )),
(1)
?
? F ?(K1 (a ), K 3 (q )) = K 2 (F (a, q )).

˜ ˜
Равенства (1) определяют отображения G' и F' только для пар ? ? E2 , ? ? E2 таких, что ?
r

˜
является кодом некоторой буквы из A, а ? является кодом некоторой буквы из B. Для ос-
˜
тальных пар отображения G' и F' доопределим произвольно. Пусть 0 = (0,!,0) . Рассмотрим
( ) ˜
автомат H = E2 , E2 , E2 , G?, F ?, 0 с каноническими уравнениями
n m r



?Z (t ) = F ?(X (t ), Q(t ? 1)),
?
?Q(t ) = G?( X (t ), Q(t ? 1)), (2)
˜
? Q(0 ) = 0 .
?
Из (1) вытекает, что если автомат D преобразует последовательность P в алфавите A в
последовательность T в алфавите B, то H преобразует код K1 (P) последовательности P в код


41
K2 (T) последовательности T. Таким образом, достаточно показать, что автоматную функцию,
задаваемую равенствами (2), можно реализовать схемой. Так как значением переменной X
являются наборы длины n из E2n , то её можно рассматривать как набор переменных
(x1, …, xn), принимающих значения из E2. Аналогично для переменных Q и Z. Тогда (2) мож-
но переписать в эквивалентном виде для некоторых функций алгебры логики fi, gj:
? zi (t ) = f i (x1 (t ),!, xn (t ), q1 (t ),! , q? (t )), i = 1,!, m,
? r
?
?q j (t ) = g j (x1 (t ),!, xn (t ), q1 (t ),!, q? (t )), j = 1,! , r.
? r


Тогда можно построить схему из функциональных элементов в базисе {?,&, } с n + r вхо-
дами и m + r выходами, реализующую семейство функций
? zi = f i (x1 ,!, xn , q1 ,!, qr ), i = 1,!, m,
? ?
?
?q j = g j (x1 , !, xn , q1 ,!, q? ), j = 1,!, r.
? r


Пусть в этой СФЭ входная переменная q?j приписана вершине vj, а выходная переменная qj
— вершине wj. Добавим дугу (wj, vj) и сопоставим вершине vj элемент задержки. Проделав
это для всех пар q j , q?j ( j = 1,!, r ) , получим СФЭЗ, функционирование которой описывается
каноническими уравнениями
? zi (t ) = f i (x1 (t ),!, xn (t ), q1 (t ? 1),!, qr (t ? 1)), i = 1,!, m,
?
?q j (t ) = g j (x1 (t ),!, xn (t ), q1 (t ? 1),! , qr (t ? 1)), j = 1,!, r ,
? q j (0 ) = 0.
?
Эта схема является искомой. Теорема доказана.

§38. Теорема Мура. Теорема об отличимости состояний двух автоматов.
Будем рассматривать автоматы, в которых не выделено начальное состояние, то есть ав-
томат задаётся пятёркой (A, B, Q, G, F).
Через A* будем обозначать множество всех конечных слов в алфавите A. Расширим
функции F и G, определив F (a , qi ) и G (a , qi ) для любого состояния qi ? Q и любого слова
a = (a(1), a (2),!, a(m )) ? A? . Пусть автомат (A, B, Q, G, F) находится в состоянии qi ? Q и на
вход подаётся слово a = (a(1), a (2),!, a(m )) . Тогда на выходе будет последовательно выда-
ваться некоторое слово b = (b(1), b(2),!, b(m )) и после подачи всего слова a автомат окажет-
ся в некотором состоянии qk. Расширим функции F и G, положив F (a , qi ) = b , G (a , qi ) = qk .
Определение 1. Два состояния qi и qj автомата (A, B, Q, G, F) называются отличимыми,
если существует входное слово a ? A? такое, что F (a , qi ) ? F (a , q j ). При этом слово a назы-
вают экспериментом, отличающим qi и qj, а длину l (a ) — длиной этого эксперимента.
Лемма. Пусть в автомате (A, B, Q, G, F) есть 2 состояния qu и qv, отличимые экспери-
ментом длины p и не отличимые более коротким экспериментом. Тогда для любого k, где
1 ? k ? p, существуют 2 состояния, отличимые экспериментом длины k и не отличимые более
коротким экспериментом.
Доказательство. Пусть состояния qu, qv отличимы экспериментом a длины p и не от-
личимы экспериментом меньшей длины. Пусть F (a , qu ) = b , F (a , qv ) = c . Тогда b ? c , при-
чём b и c различаются только последней буквой. Разобьём все слова a , b , c на 2 подслова
a = a1a2 , b = b1b2 , c = c1c2 , где l (a2 ) = l (b2 ) = l (c2 ) = k . Пусть G (a1 , qu ) = q? , G (a1 , qv ) = q?? . Тогда
F (a2 , q?) = b2 , F (a2 , q??) = c2 . Так как b2 и c 2 различаются последней буквой, то q' и q'' отли-


42
чимы экспериментом длины l (a2 ) = k . Допустим, что q' и q'' отличимы экспериментом a3
l (a3 ) < k . F (a3 , q??) = c3
F (a3 , q?) = b3 , b3 ? c3 .
длины Тогда и Но тогда
F (a1a3 , qu ) = b1b3 , F (a1a3 , qv ) = c1c3 и b1b3 ? c1c3 . Следовательно, qu и qv отличимы эксперимен-
том a1a3 длины l (a1a3 ) = l (a1 ) + l (a3 ) < ( p ? k ) + k = p . Это противоречит условию. Значит (от
противного), q' и q'' не отличимы экспериментом длины меньшей, чем k. Лемма доказана.
Теорема 3 (Теорема Мура). Если в автомате (A, B, Q, G, F) состояния qi и qj отличимы
и |Q| = r, то существует эксперимент a , отличающий qi и qj, длины l (a ) ? r ? 1 .
Доказательство. Пусть состояния qi и qj отличимы экспериментом длины p и не отли-
чимы более коротким экспериментом. Рассмотрим в данном автомате следующее отношение
Rm на множестве состояний Q (m = 0, 1, …, p): состояния qi и qj не отличимы экспериментом
длины m (считаем, что любые 2 состояния не отличимы экспериментом длины 0). Если для
любого слова a ? A? длины m F (a , qi ) = F (a , q j ) и F (a , q j ) = F (a , qk ) , то F (a , qi ) = F (a , qk ) ,
поэтому Rm — это отношение эквивалентности для каждого m = 0, 1, …, p. Относительно Rm
Q разбивается на классы эквивалентности Q1(m ), Q2m ) ,!, Qs((m)) , так что любые два состояния из
( m


одного класса не отличимы экспериментом длины m, а любые два состояния из разных клас-
сов отличимы экспериментом длины m. При этом s(0) = 1 и Q = Q1(0 ) . Посмотрим, как меня-
ются эти классы при переходе от m к m + 1. Если 2 состояния отличимы экспериментом дли-
ны m, то они отличимы и экспериментом длины m + 1, поэтому состояния из разных классов
остаются в разных классах. По лемме для любого m = 0, 1, …, p – 1 существуют 2 состояния,
отличимые экспериментом длины m + 1 и не отличимые экспериментом длины m. Следова-
тельно, хотя бы один из классов эквивалентности относительно Rm распадается не менее чем
на 2 класса эквивалентности относительно Rm+1. Отсюда
1 = s (0) < s (1) < s (2) < … < s (p – 1) < s (p) ? r.
Так как все s (i) — натуральные числа, то p ? r – 1. Теорема доказана.
Следующий пример автомата показывает, что оценку r – 1 в теореме Мура в общем слу-
чае улучшить нельзя. Здесь, независимо от входного символа a F(a, qi) = 0, для i = 2, 3, …, r и
F(a, q1) = 1.
0,1 0 0 0 0

q1 q2 q3 qr–1 qr
0
1 0 0 0 0

1 1 1 1 1

Для того, чтобы отличить состояния qr–1 и qr надо перевести хотя бы одно из них в q1
(входным словом длины r – 2) и затем подать ещё один входной символ. Следовательно, ми-
нимальная длина эксперимента, отличающего qr–1 и qr, равна r – 1.
Определение 2. Пусть 2 автомата (A, B, Q1, G1, F1) и (A, B, Q2, G2, F2) имеют одинако-
вые входной и выходной алфавиты. Пусть qi ? Q1 и qj ? Q2. Будем говорить, что эксперимент
a ? A? отличает состояния qi и qj, если F1 (a , qi ) ? F2 (a , q j ).
Теорема 4. Пусть даны 2 автомата (A, B, Q1, G1, F1) и (A, B, Q2, G2, F2). Пусть |Q1| = r,
|Q2| = m и qi ? Q1, qj ? Q2. Тогда, если qi и qj отличимы, то существует отличающий их экспе-
римент a длины l (a ) ? r + m ? 1 .
Доказательство. Можно считать, что Q1 ? Q2 = ?. Рассмотрим автомат (A, B, Q, G, F), в
котором Q = Q1 ? Q2 и диаграмма которого получается объединением диаграмм исходных
автоматов. Тогда |Q| = r + m и по теореме Мура qi, qj отличимы экспериментом a длины
l (a ) ? r + m ? 1 . Теорема доказана.



43
Следующий пример автомата показывает, что оценка r + m – 1 в общем случае не улуч-
шаема. Здесь предполагается m ? r и опять выходной символ зависит только от текущего со-
стояния и не зависит от входного символа.
0,1 0 0 0

q1? q2? qr–1? qr? qr+1? qm–1? qm?
0 0 0 0
… 0
1 0 0 0 0 0 0
1 1…1 1
1
1
1


?
Легко видеть, что если не использовать состояние qm второго автомата, то нельзя отли-
?
чить состояния q1 и q1 . Поэтому для того, чтобы отличить q1 и q1? сначала надо перевести
второй автомат словом a из q1 в q? . При этом l (a1 ) ? m ? 1 и первый автомат под действием
? m

a перейдёт из q1 в qr. Чтобы далее получить различные выходные последовательности, надо
перевести первый автомат из qr в q1 и подать ещё один символ. Всего для того, чтобы отли-
?
чить q1 от q1 потребуется входное слово длины (m – 1) + (r – 1) + 1 = m + r – 1.




44

<<

стр. 2
(всего 2)

СОДЕРЖАНИЕ