d9e5a92d

Автоматные функции

2п [2п log п\
L(E/)6-- + 0 g '
Доказательство. Разобвем набор БП х = (ад,... , хп) на подна-борві х' = (ад,..., ад) и х = (ar*+i,..., хп), где к, Ікп, некоторвій параметр. Для любого набора а' = (од,... , од) из Вк положим:
fapx) = f (а1, х).
Тогда для ФАЛ / будет справедливо представление:
/(Д; х) = V Хр ¦ . . . ¦ Хр ¦ fa'(x) = рк(хГ, Д(х) (т'=((ті ,...,(гк)евк
7.1)
Построим СФЭ Еf из универсального многополюсника Y порядка (го к) от БП х и мультиплексора Е' порядка к с адресными БП Л, на информационные входы которого подаются выходы Y в соответствии с (7.1) (см. рис. 7.1).
Если мультиплексор Е' построить по лемме 5.2, а универсальный многополюсник Y по теореме 5.4, то
L(S')3 ¦ 2к + 0(к ¦ 2*/2), ЦЕ)22Д Следовательно, полагая
к =\п log (го 2 log го)[,
получим
+о(,г.2/2)+?;=б.7:+о'
п1 п \ п1
L(E/)6---
п 2 log п
Теорема доказана. Хк-\-\ Хп
Следствие. Ь(п)6 ¦ f + O(^)F).
Рассмотрим теперь вопрос о нижних оценках функции Шеннона Ь(п) и сложности некоторых конкретных ФАЛ.


Пусть 7(L, гг) число всех тех попарно неизоморфных неприводимых СФЭ с входными БП ад,..., хп и выходной БП zi, сложность которых не больше, чем L.
Лемма 7.1. При любых натуральных L, n справедливо неравенство
7 (L.n)(L+n)2i+4.
Доказательство. Пусть Е неприводимая СФЭ с входными БП
.г і......?„ и выходной БП : |. для которой L (Е) L. Для задания СФЭ Е
достаточно:
1) выбрать целые неотрицательные числа L\. L-. L:, так, чтобы L\ + Ь-2 + Lib, это можно сделать не более, чем (L+ I)4 способами;
2) взять LI ФЭ , L-2 ФЭ V и L:, ФЭ -і, а затем каждых! вход каждого из них "присоединить" к выходу некоторого другого ФЭ или к одному из входов Е это можно сделать не более, чем (L + n)'2L способами;
3) поместить единственных! сток СФЭ Е к выходнохі БП z\.
Следовательно,
7(Т п)(L + I)4 ¦ (L + n)2L(b + n)2L+A.
Лемма доказана.
Лемма 7.2. При любых натуральных L.n справедливо неравенство: 7(Тп)(32Д+п))і+1.
Доказательство. Пусть Е неприводимая СФЭ е входными БП ... ,хп и выходнохі БП zi, для которой L(E) = VL. Сопоставим СФЭ Е ориентированное корневое упорядоченое помеченное дерево Т). получающееся из графа Е в результате "снятия" входных БП е истоков Е, "отсоединения" от каждой вершины ? графа Е, такой, что d+(v) 1, каких-либо (d+(v) 1) исходящих из нее дуг и объявления начальных вершин этих дуг новыми вершинами-листьями Т (ем. рис.

7.2). Заметим, что пометки внутренних вершин дерева Ртипами ФЭ базиса Eq сохраняются, и что в каждую такую вершину Т) е пометкой ФС -1 входит одна дуга, а е пометкой или V две дуги.
Заметим также, что для получения СФЭ Е из дерева Т достаточно каждыхі лист Т присоединить либо к одноіх из входных вершин СФЭ Е, помеченных БП жі, Х2,... , хП1 либо к одноіх из внутренних вершин самого дерева Т.
Из построения дерева Т следует, что число внутренних вершин (т. е. вершин, отличных от листьев) в нем равно V, а число ребер не больше, чем 21/, и поэтому число листьев в ТУ не больше, чем V + 1 (ем. §2). Следовательно, число различных СФЭ Е, связанных е одним и тем же деревом Т). не больше, чем (L1 + n)L+1, а из §2 вытекает, что число различных деревьев Т рассматриваемого вида не больше, чем
^2Ь ш 9І' _ 95V
Следовательно,
#,й) Е 321'(Г + п)?+1 (32(L + n))-4+1.
L=1
Лемма доказана.



Рис. 7.2
Доказательство двух следующих утверждении основано на т.н. "мощноетном" принципе получения нижних оценок функции Шеннона.
Теорема 7.2. Для любого натурального п справедливо неравенство
Цп)
Доказательство. Из определения функции Шеннона Ь(п) и величины 7(L, п) следует, что
Логарифмируя это неравенство и применяя лемму 7.1, получим:
(2L{n) + 4) ¦ log(L(n) + п)2п откуда в силу теоремы 7.1 вытекает, что
(2L(n) + 4) ¦ (го + о(1))2.
Следовательно,
Цп)(1 - о(1))
ТЪ
Лемма доказана.
Теорема 7.3. Для любого натурального п справедливо неравенство:
Доказательство. Рассмотрим множество состоящее из тех
ФАЛ /, / ? Р-2 (п), для которых
ЦЛЦп) = Ь'(п) - п
где
Из (7.2), определения величины j(L, го) и леммы 7.1 следует, что
|Р2(п)і7(І(и),п)(32Т(п))і'().
Логарифмируя (7.4) и используя (7.3), получим:
log \P2(n)\L'(п)(п - log ro + 5 + о( 1))
log го 5 о(1)
7.4)
2„/1 + lg-6\
го
го
го
Следовательно,
I В(п
2" log Iр2{п)\ -4 00 и
-э О
92
при го 4 оо, а значит, множество Р-2(п) \ Р-2(п) не пусто при достаточно больших го, и поэтому найдется такая ФАЛ /, / G р2Іп)і для которой
L(J) L(n) = - 1 +
ГО \
¦7п / logn - 6 - о(1)\
го
1 А.5)
Теорема доказана.
Следствие. Неравенство (7.5) выполняется для почти всех ФАЛ / из р2{п).
Рассмотрим теперь некоторые методы получения нижних оценок сложности конкретных ФАЛ. Соображения, связанные е тем, что сложность СФЭ Е, которая реализует систему из т различных ФАЛ, отличных от БП, не может быть меньше, чем тго, мы уже использовали в теоремах 5.1, 5.3.

В случае дешифратора, а также в некоторых подобных случаях эту тривиальную оценку можно несколько уточнить.
Лемма 7.3. Сложность схемного дешифратора порядка го, го 2, не меньше, чем 2п + л/2 ¦ 2пР го 1.
Доказательство. Пусть Е строго приведенный схемный дешифратор порядка го, го 2, е входными БП жі,..., хп. Из строгой приведенности Е следует, что каждый его выходной ФЭ является либо ФЭ , либо ФЭ -1. Действительно, если бы на выходе ФЭ V СФЭ Е реализовалась конъюнкция К = хр ¦ ... ¦ хр, то хотя бы на одном из его входов также реализовалась бы конъюнкция К. и в СФЭ Е оказалось бы две различных эквивалентных вершины (ем. §4).

По этой же причине на входы всех двухвходовых ФЭ СФЭ Е подаются различные ФАЛ. Заметим также, что выход ФЭ €’, который одновременно является выходом Е, не может поступать на вход другого ФЭ
S, выход которого также является ввіходом Е, т.к. при этом ФЭ S' и S должнві бвітв ФЭ или -1, на ввіходах которвіх реализуются разнвіе конъюнкции из Qn, что невозможно. Пуетв а число вершин СФЭ Е, отличных от ее ввіходов. Из указаннвіх особенностей СФЭ Е следует, что
Ппа(а 1) а (а + 1)
" 2 а 2 5
и поэтому
ау/2-2п/2- 1
Таким образом,
ЦЕ)2 + а - п2п + sf2 ¦ 2п/2 - п- 1.
Лемма доказана.
Следствие. В силу следствия 2 из теоремы 5.1
2п + \р2 ¦ 2п2 -п- lL(Qn)2n + |?/2 ¦ 2п2 + 0(п ¦ 2п/4).
Лемма 7.4. Если СФЭ Е реализует существенную ФАЛ f(xі,... ,т„) , mo L(E) гг 1, а если, кроме того, ФАЛ / немонотонна, то L(E) гг.
Доказательство. Переіадем от СФЭ Е, еодержащеіі ФЭ и V, к дереву 22 так, как это бвіло сделано при доказателветве теоремві 7.1. Заметим, что число БП / не болвше, чем число лиетвев дерева Т). которое, в свою очередв, не болвше, чем L" + 1. Следователвно,
L(Yj)Ln 1.
Если же в СФЭ Е еетв хотя бві один ФЭ -і (в том случае, когда ФАЛ / немонотонна, ФЭ -і в СФЭ Е обязателвно найдется), то
L(E)L + In.
Лемма доказана.
Применяя лемму 7.3 к ФАЛ / = х\ V... ?ж„, получим, что L(f)n. С другой еторонві, ФАЛ / можно реализоватв формулой х\ ¦ ... ¦ хп, и поэтому L(f) п. Следователвно, формула х\ ¦ ... ¦ хп является мини-малвной (в классе СФЭ), и L(f) = п.
Будем говоритв, что подмножество U множества БП ФАЛ / забивает БП х, х ^ U. ФАЛ /, если подстановки некоторвіх констант вместо БП U из ФАЛ / можно получитв ФАЛ, не зависящую существенно от х. Множество переменнвіх X ФАЛ / будем назвіватв неза-биваемым, если любая переменная х из X не забивается множеством
Х\{ж}. Легко видеть, что при любой подстановке констант вместо некоторых переменных незабиваемого множества X ФАЛ / оставшиеся переменные из X образуют незабиваемое множество переменных для ФАЛ, получающейся в результате этсш подстановки. Очевидно также, что все переменные незабиваемого множества X ФАЛ / являются существенными переменными /, если |Х| 2.
Теорема 7.4. Если у ФАЛ / есть незабиваемое подмножество из п переменных, то
Щ)2(п-1).
Доказательство. При п = 1 оценка теоремы, очевидно, верна. Предположив, что эта оценка верна для любой ФАЛ / и любого п (1 1), где I 2, докажем ее справедливость для произвольной ФАЛ h, которая имеет незабиваемое подмножество, составленное из существенных переменных ад,..., хі ФАЛ h. Пусть Е минимальная СФЭ, реализующая ФАЛ h со сложностью L(h).

Рассмотрим вершину ? СФЭ Е, в которую ведет дуга из входной вершины ад, и которой приписана ФАЛ р базиса Eq. Пусть а = 0. если р = щ ¦ щ, и и = 1 в остальных случаях. Вершина ? не может быть выходом Е, так как иначе при ад = а на выходе Е появлялась бы константа и переменная ад забивала
бы, тем самым, переменные ад......г/ ФАЛ І. Следовательно, найдется
вершина ш СФЭ Е, в которую ведет дуга из вершины ?. Пусть Е? СФЭ, получающаяся из СФЭ Е в результате подстановки константы3 а вместо переменной ад. Схема Е/ реализует некоторую ФАЛ // с незабиваемым множеством из переменных ад, ¦ ¦ ¦ и не содержит вершин ?, w, то есть имеет сложность не более, чем L(Е) 2. В силу индуктивного предположения L(f ) 2(1 2), и поэтому
L(h) = L(E)L(E') + 2L(f') + 22(I - 1).
Теорема доказана.
Следствие. Ь(цп) = 2 ¦ 2 + 0(2/2).
Деійствительно, требуемая верхняя оценка для Ь(/іп) вытекает из теоремы 5.2 (см. следствие), а так как БП г/о,..., У2п-і образуют незабиваемое множество БП /г„, то теорема 7.3 дает необходимую нижнюю оценку.
3Подстановка констант вместо некоторых входных переменных СФЭ подразумевает, что ‘‘константные" входы схемы, а также те элементы, на входах которых появляются константы, последовательно устраняются применением тождеств 0 = 1, 1 = 0, ж - 0 = 0, ж V 1 = 1, і ¦ 1 = і ?0 = г до тех нор, пока это возможно.
Рассмотрим, в заключение, вопрос о сложности реализации симметрических ФАЛ.
Функция f(x 1,..., хп) назвівается симметрической, если ее значение не меняется при любой перестановке аргументов. Значение симметрической ФАЛ однозначно определяется числом единиц в наборе значений ее переменнвіх, так как два набора с одинаковвім числом единиц всегда можно получитв друг из друга некоторой перестановкой аргументов.

Заметим, что любая отличная от константві симметрическая ФАЛ f(xі,...,хп) является существенной ФАЛ, и поэтому L(f) п 1 согласно лемме 7.3.
Теорема 7.5. Любую симметрическую ФАЛ от п переменных можно реализовать со сложностью 9п + О -
Доказательство. Пуетв /(ад,... , хп) симметрическая ФАЛ, k =] log2(n + 1)[, а ФАЛ д(уъ ...,ук) на наборе а = (аь ..., од), где |а| гг, равна значению ФАЛ / на наборах с |а| единицами и принимает произволвнвіе значения на осталвнвіх наборах.

Пуетв Е/ счетчик е входивши переменивши х\,... ,хп (ем. замечание к теореме 6.3) сложности не более, чем 9(п + к'2), а СФЭ, реализующая ФАЛ д и имеющая сложности не более, чем 6(1 + о(1))у (ем. теорему 7.1). Схема Е/, которая получается присоединением ввіходов СФЭ Е/ к входам СФЭ Е??. реализует, очевидно, ФАЛ /, и
' C)k '
к
L(E/) = L(E') + L(E)9n + О
Jog го,
Теорема доказана.
Часть 3. Автоматы

§ 8. Автоматные функции. Их реализация схемами из функциональных элементов и элементов задержки


В данном параграфе рассматриваются некоторые вопросы, евя-заннвіе с автоматами и осуществляемыми ими отображениями. Подробное изложение теории автоматов можно найти в (?) . В (?) рассматриваются автоматнвіе отображенияия и операции над ними.

Здеев мві рассмотрим евязв между автоматнвіми отображениями и схемами из функционалвнвіх элементов и элементов задержки.
Определение. Инициальным автоматом назвіваетея любая шестерка (Л. В. Q. G. F. до). где А. В, Q - произвольные множества, G функция, отображающая пары из декартова произведения А X Q в Q, F функция, отображающая пары из А X Q в В, и go G Q. Множества А, В, Q называются, соответственно, входным алфавитом, выходным алфавитом и алфавитом (множеством) состояний.

Функция G называется функцией переходов, функция F функцией выхода, до называется начальным состоянием.
Определим функционирование автомата. Будем рассматривать параметр t, принимающих! значения 0,1,2,... , который можно интерпретировать как дискретное время. Будем считать, что на вход автомата может поступить любая последовательность а(1), а(2), а(3),... (конечная или бесконечная), где a(t) G А для всех t. Введем переменные q(t), і = 0,1,... и z(t), t = 1.2.....которые будем называть
состоянием автомата в момент і и выходным значением в момент t. Пусть x(t) значение входа в момент t. Тогда определим z(t) и q(t) равенствами Эти равенства называются каноническими уравнениями автомата.
Легко видеть, что из канонических уравнений по х{1) и д(0) = до однозначно определяются г(1) и д(1). Затем по д(1) и х(2) однозначно определяются z(2) и д(2) и т.д. В результате по входной последовательности ж(1), ж(2),... , х(п) однозначно определяется выходная последовательность z(l), z(2),..., z(n), то есть автомат осуществляет отображение последовательностей любой длины (конечной или бее-конечной) е элементами из А в последовательности той же длины е элементами из В.
Определение. Пусть А ж В два множества.

Отображение последовательностей е элементами из А в последовательности е элементами из В называется автоматной функцией, если существует инициальных! автомат, осуществляющих! это отображение.
Пример. Пусть А = В = Q = {0,1} и автомат описывается следующими каноническими уравнениями
' z(t) = q(t - 1)
q(t) = (8-2). g(0) = 0.
Легко видеть, что входная последовательность а(1), а(2), а(3),... отображается таким автоматом в последовательность 0, а(1), а(2),.... Этот автомат называется единичной задержкой.
Автоматы удобно задавать геометрически е помощью ориентированных графов. При этом каждому состоянию из множества Q сопоставляется вершина орграфа, и каждой паре (а,д), где а ? А, q ? Q сопоставляется дуга, идущая из вершины, соответствующей д, в вершину, соответствующую G(a, д).

Этой дуге приписывается пометка (a, F(a,q)). Вершина, соответствующая начальному состоянию до, помечается (мы будем помечать ее звездочкой).

Описанных! граф е пометками называется диаграммой Мура заданного автомата. Например, на рис.

8.1 представлена диаграмма Мура для задержки.
Легко видеть, что диаграмма Мура однозначно задает автомат. По дугам и пометкам на дугах однозначно определяются функции переходов и выхода.
Рассмотрим теперь класс схем, е помощью которых можно реализовать автоматные функции.
Определение. Пусть задан базис Б={?і,..., Ss, R}, где Si,... ,Ss функциональные элементы (ем. параграф 4), a R элемент единичной задержки, имеющих! один вход и один выход. Схемой из функциональных элементов и элементов задержки (СФЭЗ) в базисе Б называется граф, которых! удовлетворяет пунктам 1)-3) определения
СФЭ (см. стр. ?) и в котором любой ориентированных! цикл проходит хотя бві через одну вершину, соответствующую элементу задержки.
Будем ечитатв, что все переменнвіе СФЭЗ принимают значения из множества {0,1} и могут менятв их в моментві времени t = 1,2,.... При этом функционирование элемента R опиевіваетея уравнениями (8.2), а функционирование ФЭ имеющего /у входов, по-прежнему опиевіваетея ФАЛ (рі(щ,... , м^), г = 1.....*. Для описания функци
онирования СФЭЗ е г элементами задержки R поступим следующим образом.
Пуетв і-я задержка і?,, / = 1.....г, приписана вершине и,, в ко
торую идет дуга из вершины ш,. Для всех і = 1,..., г удалим из СФЭЗ дуги (ш,, ъ’і). По определению СФЭЗ в полученном после этого графе не будет ориентированнвіх циклов и он, тем еамвім, будет предетавлятв собой СФЭ.

Входами этой СФЭ будут все входві исходной схемы, а также все вершинві и,, і = 1,..., г (заметим, что все они различнві и отличнві от входов исходной ехемві). Ввіходами полученной СФЭ
объявим все ввіходві исходной ехемві и вершинві шг, і = 1.....г. Пуетв
в исходной схеме ввіходам приписанві переменнвіе zi,..., zm, входам переменнвіе ад,..., хп. Вершинам и,- припишем переменнвіе q[,..., g{, а вершинам ш, переменнвіе gi,..., qr. В соответствии е определением функционирования СФЭ, для некоторвіх ФАЛ /г, (jj справедливо:
f %i fi(*^І5 - - - 5 ¦ Ч\.....Qr) Л 1,... , тп (8 3)
1 Qj = 9j(xh - - - 5 xnj Q\j - - - 5 Qr)jj = 1, - - - , r.
Естественно ечитатв, что равенства (8.3) ввіполняютея в каждый момент времени t = 1.2.3.....то еетв
Иі = ¦¦ ^Xnit),^),... = 1,... ,r.
Так как, в соответствии е каноническими уравнениями (8.2), ввіход элемента задержки в момент t совпадает е его входом в момент t 1, то естественно ечитатв, что в исходной схеме q[{t) = qi(t 1) при і = 1, 2,... для всех і = 1,..., г, где дг(0) = 0. Тогда равенства (8.4) принимают вид (где і = 1.....іи и j = 1.....г):
*i(t) = /;-(^i(t),...,T„(t),gi(t- l),...,gr(t- 1)),
' Qj(t) = 9j(xi(t),---,xn(t),qi(t-l),...,qr(t-l)), (8.5)
. Ф) = 0.
Полученнвіе равенства определяют функционирование СФЭЗ и назві-ваются ее каноническими уравнениями.
Пример. СФЭ Е' на рис.

4.46 является ячейкой сумматора и реализует ФАЛ z\ = ху V xq' V yq!, z-j = х ® у ® q!. Тогда схема на рис. 8.2 будет иметь канонические уравнения
z(t) = x(t) ? y(t) ? q(t - 1)
- q(t) = x(t)hy(t) V x(t)hq(t 1) V y(t)hq(t 1)
. g(0) = 0.
Если на входы хи у этой СФЭЗ подавать два двоичных числа по одному разряду в каждый момент времени, начиная е младших разрядов, то на выходе схемы будет выдаваться сумма этих чисел, начиная е младших разрядов. Эта схема называется последовательным сумматором.
Пусть Еф множество всех наборов длины п с элементами 0 и 1. Если задана последовательность наборов из Е% в качестве значений
входных переменных хфб), / = 1.....п. і = 1,2,..., то согласно (8.5)
по ним однозначно определяется последовательность наборов длины т zi(t),..., zm(t) для t = 1, 2,.... Таким образом, схема осуществляет преобразование последовательностей е элементами из Еф в последовательности е элементами из Е™.
Определение. Пусть автоматная функция р отображает последовательности в конечном алфавите А в последовательности в конечном алфавите В. Пусть СФЭЗ Е осуществляет преобразование ф последовательностей е элементами из Е% в последовательности е элементами из Е™. Будем говорить, что Е моделирует р, если существуют отображения (кодирования) К\ : А Еф и /С : В Еф. сопоставляющие разным элементам разные элементы и обладающие свойством: для любой последовательности Т = а(1)а(2) ... a(t) в алфавите А. если р(Р) = R = Ь(1)Ь(2)... b{t), то ф(Кі(Р)) = К^ІТ), где
ЩР) = АЭ((1))ІС(а(2))... Аі(М),
К2(Т) = К2(Ь(1))К2(Ь(2))... K2(b(t)).
Теорема 8.1. 1) Отображение, осуществляемое любой СФЭЗ, является автоматной функцией.

2) Для любой автоматной функции существует моделирующая ее СФЭЗ в базисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элемента задержки.
Доказательство. 1) Пусть отображение ф, осуществляемое схемой Е, задается каноническими уравнениями (8.5).

Введем переменные X = (ад,..., хп), Q = (ді,... , gr), Z = (zj,..., zm), принимающие значения, соответственно в ЕД, ЕД, ЕДЕ Положим до = (0,..., 0). Тогда (8.5) можно переписать в виде
' Z(t) = F(X(t).Q(t-l))
¦ Q(t) = G(X(t),Q(t- 1))
. 3(0) = о,
где функции F. G не зависят явно от і. Отсюда видно, что отображение, осуществляемое схемой, совпадает с отображением, задаваемым автоматом (ЕД, ЕД1, ЕД, G, F, до), то есть является автоматной функцией.
2) Пусть автоматная функция дана автоматом D = (А, В, Q, G, F, до). Выберем п, т, г так, что 2|А|, 2m|E?|, 2r|Q|.

Рассмотрим произвольные отображения (кодирования) К\ : А ЕД, К2 : В ЕД1, ЕЕ3 : Q ЕД, при которых разные элементы отображаются в разные элементы. Дополнительно потребуем, чтобы -Кз(до) = (0,..., 0). Рассмотрим отображения G' : ЕД х ЕД ЕД и : ЕД X ЕД ЕД* такие, что для любых а G А и g G Q выполняется
f G'(A,().A3(g)) = A3(G(,g))
\ ІДЛЧДЛЩ)) = A'2(F(a,g)). 1 ’
Равенства (8.1) определяют отображения G' и Е^ только для пар о- G ЕД, /3 G ЕД таких, что а является кодом некоторой буквы из А, а /3 является кодом некоторой буквы из В. Для остальных пар отображения G' и F' доопределим произвольно. Пусть 0 = (0,... ,0). Рассмотрим автомат Н = (ЕД, ЕД1, ЕД, Gr, ЕД 0) с каноническими уравнениями
' Д) = C(A(f).Q(i-l))
- Q(t) = G'(X(t),Q{t 1)) (8.7)
. Q(0) = 6
Из (8.6) вытекает, что если автомат D преобразует последовательность Р в алфавите А в последовательность Т в алфавите В, то ІЕ преобразует код К](Р) последовательности Р в код К2ІД) последовательности Т. Таким образом, достаточно показать, что автоматную функцию, задаваемую равенствами (8.7), можно реализовать схемой. Так как значением переменной X являются наборы длины п из ЕД, то ее можно рассматривать как набор переменных (ад,... ,хп), принимающих значения из Е2.

Аналогично для переменных Q и Z. Тогда (8.7) можно переписать в виде (8.4) для некоторых ФАЛ /,;, gj. По теореме 4.2 можно построить СФЭ в базисе {дизъюнкция, конъюнкция, отрицание} е п + г входами и т + г выходами, реализующую семейство функций
( Д ft (*Л 5 - - - 5 5 Ql 5 - - - 5 Qr) Л 1 , . . . , ТП
\ Qj 9j (*^1 5 - - - 5 ®П) 91 5 - - - 5 Qr) 5 J 1 , . . . , Г.
Пусть в этой СФЭ входная переменная q'- приписана вершине vj, а выходная переменная qj вершине Wj. Добавим дугу (vjj,Vj) и сопоставим вершине ьд элемент задержки.

Проделав это для всех пар gj, q'j (j = 1,..., г) получим СФЭЗ, функционирование которой описывается каноническими уравнениями (8.5). Эта схема является искомой.

Теорема доказана.
Пример (ячейка памяти). Пусть требуется построить СФЭЗ для автомата с двумя входами, в котором выход в момент времени t всегда совпадает с состоянием в момент t 1, а состояние остается неизменным, если х-2 = 0 (ячейка закрыта для записи), и состояние становится равным х\, если Х2 = 0 (ячейка открыта для записи). Канонические уравнения такого автомата имеют вид
z(t) = q(t- 1)
- q(t) = X](t)x2(t) V q(t l)x2(t)
q(0) = 0.
На рис. 8.3 приведена СФЭЗ, реализующая ячейку памяти.



Рис. 8.3
Для получения памяти из 2 ячеек с записью одного бита по адресу достаточно взять 2 ячеек памяти, их входы .r-j присоединить к различным выходам дешифратора порядка го, а все входы х\ присоединить к единому входу, на который поступает записываемых! бит.
Чтобы дополнительно обеспечить считывание по адресу достаточно выходы всех ячеек подать на различные информационные входы мультиплексора порядка п.

§ 9. Эксперименты с автоматами. Теорема Мура


Будем теперь рассматривать автоматы, в которых не выделено начальное состояние, то есть автомат задается пятеркой (A.B.Q.G.F).
Через А* будем обозначать множество всех конечных слов в алфавите А. Расширим функции F и G. определив F(a, g,) и G(a, g,) для любого состояния g,; G Q и любого слова а = (а(1), а(2),..., а(т)) G А*. Пусть автомат {Л. В. (J.

G. F) находится в состоянии g* G Q и на вход подается слово а = (а(1),а(2),... ,а(т)). Тогда на выходе будет последовательно выдаваться некоторое слово 6 = (6(1), 6(2),..., 6(ш)) и после подачи всего слова а автомат окажется в некотором состоянии qk- Расширим функции F и G, положив F(a,g,;) = 6, G(a,g,;) = д.
Определение. Два состояния д,; и qj автомата (Л. B.Q.G.

F) называются отличимыми, если существует входное слово a G А* такое, что F(a, g,;) ф F(a,qj).При этом слово а называют экспериментом, отличающим д,; и ду, а длину 1(a) - длиной этого эксперимента.
Теорема 9.1 (Мур). Если в автомате {Л.

В. (J. G. F) состояния qi и qj отличимы и |Q| = г, то существует эксперимент а, отличающий д,; и qj, длины 1(a)г 1.
Лемма 9.1. Пусть в автомате (А, В, (J.

G, F) есть 2 состояния qu и qv, отличимые экспериментом длины р и не отличимые более коротким экспериментом, тогда для любого к, где 1 кр, существуют 2 состояния, отличимые экспериментом длины к и не отличимые более коротким экспериментом.
Доказательство. Пусть состояния qu,qv отличимы экспериментом а длины р и не отличимы экспериментом меньшей длины. Пусть F(a, qu) = 6, F(a, qv) = с. Тогда, 6 ф с, причем бис различаются только последней буквой.

Разобьем все слова а, 6, с на 2 подслова а = щщ, Ь = hh-, с = С]С2, где 1(а2) = 1{Ь2)_ = 1(G) = к. Пусть G(abqu) = g;, G'(c |. qv) = q. Тогда F{a-. /) = b-. f{a-. g??) = ¦¦. Так как b- и ¦¦ различаются последней буквой, то q! и q отличимы экспериментом длины 1(а2) = к. Допустим, что q' и q отличимы экспериментом аз длины /(аз) к. Тогда F(a^q') = 63, F(aZlq) = с3 и 63 ф с3.

Но тогда F(aia3,gu) = 6,63. l7{a\a:].qr) = С]С3 и 6,63 ф С]С3. Следовательно, qu и qv отличимы экспериментом щщ длины /(аДз) = /(щ) + /(аз) (р к) + к = р. Это противоречит условию.

Значит (от противного) / и q не отличимы экспериментом длины меньшей, чем к. Лемма доказана.
Доказательство теоремы Мура. Пусть состояния д* и qj отличимы экспериментом длины р и не отличимы более коротким экспериментом.

Рассмотрим в данном автомате следующее отношение Rm на множестве состоянии Q (т=0,1,...,р): состояния д* и qj не отличимы экспериментом длины т (считаем, что любые 2 состояния не отличимы экспериментом длины 0). Если для любого слова а ? А* длины т F(a,g,;) = F(a,qj) и F(a,qj) = F(a, g), то F(a,g,;) = F(a,g), поэтому
Rm это отношение эквивалентности для каждого іи = 0.1.2.....р.
Относительно Rm Q разбивается на классы эквивалентности Q\m\ Qiipyp так что любые два состояния из одного класса не отличимы экспериментом длины ш, а любые два состояния из разных классов отличимы экспериментом длины т. При этом s(0) = 1 и Q = QfK Посмотрим как меняются эти классы при переходе от т к т + 1. Если 2 состояния отличимы экспериментом длины т, то они отличимы и экспериментом длины т + 1, поэтому эксперименты из разных классов остаются в разных классах. По лемме 9.1 для любого
іи =0.1.....Р I существуют 2 состояния, отличимые экспериментом
длины т+1 и не отличимые экспериментом длины т. Следовательно, хотя бы один из классов эквивалентности относительно Rm распадается не менее чем на 2 класса эквивалентности относительно Rm+i-Отсюда 1 = 5‘(0) s(l) s(2) ... s(p 1) s(p)r. Так как все s(i) натуральные числа, то рг 1. Теорема доказана.
Пример автомата на рис. 9.1 показывает, что оценку г 1 в теореме Мура в общем случае улучшить нельзя. Здесь, независимо от входного символа a G(a, g,;) = 0, для і = 2,3,..., г и G(a, gi) = 1.



Рис. 9.1
Для того, чтобы отличить состояния gr_i и gr надо перевести хотя бы одно из них в gi (входным словом длины г 2) и затем подать еще один входной символ. Следовательно, минимальная длина эксперимента, отличающего gr_] и gr, равна г 1.
Определение. Пусть 2 автомата (Л.

В. Q\. G\.

F\) и (A, B. Q2. G2, Fj) имеют одинаковые входной и выходной алфавиты.
Пусть чі G Q\ и ц G Q‘2- Будем говорить, что эксперимент a G А* отличает состояния д* и д/. если F\ (и. д.;) ф F-{u. д/).
Теорема 9.2. Пусть дамы 2 автомата (A,B,Q\,G\,Fi), (A, B. Q2.

G2. F2).

Пусть |Q] | = г, |Q2| = т и д,: G Qi, qj G Q2. Тогда, если д,; м д^ отличимы, то существует отличающий их эксперимент а длины 1{а)г + т 1.
Доказательство. Можно считать, что Q] П Q2 =. Рассмотрим автомат (Л. B.CJ.G. F). в котором Q = Q\ U 02 и диаграмма которого получается объединением диаграмм исходных автоматов.

Тогда |Q| = г+т и по предыдущеіі теореме д/. qj отличимы экспериментом а длины 1{а)г + т 1. Теорема доказана.
Следующші пример (рис. 9.2) показывает, что оценка г + т 1 в общем случае неулучшаема.

Здесь предполагается тг и опять выходной символ зависит только от текущего состояния и не зависит от входного символа.



Рис. 9.2
Легко видеть, что если не использовать состояние /пІ второго автомата, то нельзя отличить состояния ді и q\. Поэтому сначала надо перевести второй автомат словом d\ из q\ в q!m. При этом 1{а\)т 1 и первый автомат под действием а перейдет из q\ в gr.

Чтобы далее получить различные выходные последовательности, надо перевести первый автомат из gr в д5 и подать еще один символ. Всего для того, чтобы отличить ді от д(, потребуется входное слово длины (ш 1) + (г 1) + 1 = т + г 1.
Определение. Автомат, в котором все состояния попарно отличимы, называется приведенным автоматом.
Неотличимые состояния в автомате образуют классы эквивалентности.
Определение. Число классов неотличимых состояний называется весом автомата.
Если склеить все неотличимые между собой состояния, то диаграмма корректно перейдет в диаграмму приведенного автомата, который реализует то же автоматное отображение входных слов в выходные, что и исходный автомат.
Рассмотрим следующую задачу. Дан автомат с известной диаграммой, но неизвестно его начальное состояние.

Всегда ли существует эксперимент а, позволяющих! определить это начальное состояние? Последнее равносильно тому, что F(a, g,;) ф F(a,qj) для любых состояніи! g,; ф ] j.
Теорема 9.3. Существует приведенный автомат, в котором нельзя определить начальное состояние.
Доказательство. Рассмотрим автомат на рис.

9.3. Здесь первое число в скобках обозначает входной символ, а второе выходной символ.



Рис. 9.3
Он приведенный, так как д2 отличается от ді и д; экспериментом 1, а ді отличается от д: экспериментом 0. С другой стороны, нет единого эксперимента, отличающего все состояния, так как любой эксперимент, начинающийся с 0, не отличает ді и д-_. а любой эксперимент, начинающийся с 1, не отличает ді и дз. Теорема доказана.

Литература


1. Алексеев В. Б., Ложкин С. А. Элементы теории графов и схем. М.: Изд-во МГУ, 1991. 40 е.
2. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М.: Наука, 1977. 368 е.
3. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 е.
4. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // ДАН СССР 1962. Т. 145.

N 2. С. 293-294.
5. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985. 320 е.
6. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 137 е.
7. Потемкин И. С. Функциональные узлы цифровой автоматики.
М.: Энергоатомиздат, 1988. 320 е.
8. Яб лонекий С. В. Введение в дискретную математику. 2-е изд.

М.: Наука, 1986. 384 е.
9. Яб лонекий С. В. Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986. 40 е.



Содержание раздела