В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU), страница 11

Дополнительно потребуем„чтобы Кд(ц0) = (О,...,0). Рассмотрим отображения С': Е~ х Е~ — + Е; и Г': Е~' х Е2' -+ Е~' такие, что для любых а б А и д Е Я выполняется (8.6) Равенства (8.1) определяют отображения С' и Р' только для пар Й Е Е2', 3 Е Е~ таких, что о является кодом некоторой буквы из А, а ~3 является кодом некоторой буквы из В. Для остальных пар отображения С' и Р' доопределим произвольно. Пусть О = (О,...,0). Рассмотрим автомат Н = (Е~, Е.,',", Е~, С', Р', 0) с каноническими уравнениями (8 ) Я(0) = 0 Из (8.6) вытекает, что если автомаг .0 преобразует последовательность Р в алфавите А в последовалельность Т в алфавите В, то Н преобразует код К1 (Р) последовательности Р в код К~(Т) последовагельности Т. Таким образом, достаточно показать, что автоматную функцию, задаваемую равенствами (8.7), можно реализовать схемой.

Так как значением переменной Х являются наборы длины ьз из Е~', то ее маржи~ рс!ссыа(рина»! ь как набор !н»ременных (:1, 1,...,,Г,)„Н1)ин!!к!аюьцих значения нз .Е2. Аналогично для переменных Я и К. То);»Га (8. !') можно пе1)оп!!с(гг!» н ниде (8А) для н()котор1»1х ФАЛ Л, Ж. По тео1)еме 4.2 МО»1(НО ПОСТ|)ОН'ГЬ СФЭ Н баЗИСР (дИЗ!»К)нкцня, КОН'ЬК>НКЦИЯ» ОГ1)н- цаниР).

с Г), + !' БхОдеми и )н + ! БыхОдами, 1)РБ;!изую!Пую (."('мРйс1БО функций ~! (;Г ь... » х, » (>'! „..., д,,', )» ! = 1,... » т (11 = (!.(>К1,... ».Г,„»(1)1,...,дс)» ! = 1,..., Г. Пусть н этой СФЭ входная переменная д' Приписана вершине !);„ с! БыхОдная е1(»рРменн ая щ Б(»рн!Нне ((1 !. Добс!Бим дъ1 у (1!> 1, '!)! ) и сопо(.таним нершине с элемент задержки. Проделан зто дня нсех пар щ» ~~' (у = 1»...,Г) получим СФЭЗ, функционирование кото1)ой ОШЕСЫНаРТСя КИНО!!Иснн(.'КИМИ у!)БННЕНИЯМ1! (8.д). Э1а СХРМа яаляРтея искомой.

Теорема доказана. Пример (ячейка памяти). Пусть требуется нос!1)о(ггь СФЭ3 для автомата с двумя нходамн, н котором выход в моме!п нремени 1 всегда совпадает с состоянием н момент 1 — 1„а состояние остаетсн неизменным, если х2 = О (ячейка закрыта для записи), и состояние становится равным х!» если !> = О (ячейка открыта для записи). 1~»с!НОНН»1(»(..КИЕ у1)аННЕНИЯ ГБКОГО БН!ОМЕ(>а ИМЕИ)т Ннд На рис.

8.3 принедена СФЭЗ, реализую!цая ячейку памяти. ,Г'! ХЗ Рис. 8.3 Для полу !ения памя!и из 2" ячеек с занисьн) одного би:Га по адресу ДО(Тсиос!НО БЗ>ГГЬ 2'" ЯЧЕЕ»К Пса%!>1ТИ» ИХ ВХОДЫ Х~ П1)ИСО(»ДИН!>П!» К различным Выходам д(шифратора порядка и» а Б(.е Входы»Б1 присоединить и (»диному Входу, на который поступает запи(1»1наемый бит. Чтобы дополнительно обеспечить считывание по адресу достагочно выходы всех ячеек подать на различные информационные входы мулыиплексора порядка и. ~ 9. Эксперименты с автоматами.

Теорема Мура Будем теперь рассматривать автоматы, в которых не выделено начальное состояние, то есть автомат задается пятеркой (А, В., Я., С, Г). Через А* будем обозначать множество всех конечных слов в алфавите А. Расширим функции Г и С, определив Г(и, у;) и С(а, у,) для любого состояния у; Е Я и любого слова а = (а(1), а(2),..., а(тп)) Е А*. Пусть автомат (А,В,©С,Г) находится н состоянии у; Е Я и на вход подается слово а = (и(1), а(2) ....., и(ю)).

Тогда на выходе будет последовательно выдаваться некоторое слово 6 = (6(1),6(2),...,6(т)) и после подачи всего слова и автомат окажется в некотором состоянии ут,. Расширим функции Г и С, положив Е(а, у;) = 6., С(и„у;) = ут,. Определение. Два состояния у; и у. антомага (А„В,фС,Е) называются отличимыми, если сушестнует входное слово а Е А* такое, что Е(а, у;) ф г'(а, у.). При этом слово и называют экспериментом, отличакнцим у; и у, а длину 1(й) — длиной этого эксперимента. Теорема 9.1 (Мур). Если в ивтпомите (А.В,Я,С,Г) состояния у,; и у, отличимы и Д = г, то существует экспериментп и, отпличиющиЬ у; и у;.

длин,ы 1(и)г — 1. Лемма 9.1. Пусть в автомитпе (А, В, Я, С, Г) есть 2 состояния у„и у„отличимые эксьзериментпом длины р и не отличимые более коротким экспериментом, тогда для любого 1с. где Ир, существуютп 2 состполния, отпличимые экспериментом длины 1. и нс отличимые более коротким экспериментом. Докиэитт~ельство. Пусть состояния у„,у, отличимы экспериментом а длины р и не отличимы экспериментом меньшей длины. Пусть Г(и„у„) = 6, Е(а,у,) = с.

Тогда, 6 ~ с, причем 6 и с различаются только последнеи буквой. Разобьем все слова а, 6, с на 2 подслона а = и1аз, 6 = 616з, с = с1сз, где Циз) = 1(6з) = 1(сз) = Й. П~сть С(й1, у„) = у., С(а1,у.„) = у . Тогда Е(аз,у) — 6з, Д(аз,у ) = сз. Так как 6з и сз различаются последней букной, то у' и у" отличимы экспериментом длины Цаз) = Е Допустим, что у' и у" отличимы экспериментом из длины 7(аз) < Е Тогда Г(аз,У') = 6з, Е(из,Ул) = сз и 6з ф сз. Но тогда Е(а1аз> у„) = 6т6з, Г(а1из, у.„) = с1 сз и 616з Ф с1сз.

Следонагельно, ()„7$ д( оЕличнмы экспериментом ($1()1 длины Ца(ав) = [(а1) + ц((ЕВ) < (р — Й) + А = р. Это противоречит условию. Значит (от противного) д' и ([" не отличимы экспериментом длины меныпей, чем Й. Лемма дОка,нана. Дакаа()телье)7)на теоремы Мур(е. Пусть ( остояния у; н (7 О!В!1(ч$(- мы экспериментом длины р и не отличимы более коротким зкспернментом. Рассмотрим в данном автома)е с.!(!дую!1!ее о!но!пение Л„, на множестве.

~о~тоя~~й (~ (777=0,1,...,р): со(.тояния ф и ф не от;,1ичимы зксперим( нтом длины ш (считаем, что;побые 2 состояния не отличимы экс$1ериыентом Дчие(ы О). Если Для лк)60ГО слОВа Й ~ А д1$$1(ь$7)е Г(а.,ц) = Г(а,,() ) и Г(а.д.) = Г((1, д$). то Г(а,(7$) = Г(а,()ь), позГому Л„, — это отно!пение эквивалентности для каждого 771 = 0„1,2,...,р. Относительно Л.„, Я разбнвается на кла(есы эквивалентности ЯЕ [т) С~2,...„с 7 [ „р 'Гак '$$0 лк)бы(' два (Остояния из одно!О ке!а()се! не Отличимы экс$1ер$»ментом длины 7н, а лк)бые два со(*'Гояння ич 1)азнь$х классов отличимы экспериментом длины 777, Прн этом в(0) = 1 и Я = Я1 . Посмот[)им как меня!от(я '.)ти кла(.сы при 11ереходе От Ен [0$ к 777+ 1.

Е(.ли 2 состояния оч)личимы экспериментом длины Ен, то они отли~им~ и экс11ери~(енЕОКЕ Дчины 777 + 1. Поэ!Оые( зкспер$(~1( нты из разньЕХ кла(х.ов Остак)ЕСЯ в разных ~ла~~~~. По лемме 9.1 для ~~бого 77$ = О, 1,..., $) — 1 суп$ествуют 2 со('тояния, От)$ичи$(!ьЕе зксперим()е(том д чины 777+ 1 и не Оч чичимые зксперименчом ч чины н) С чедовиге чье(О хо'Гя бы Од)!н иэ классОВ эквивалентности ОтеЕОси'Гельно Л777 распаде1- ется н( менее чем на 2 класса эквивалентно(еги относительно Л„,»1.

Отсюда 1 = в(0) ( в(1) в(2) <... <, В(р — 1) ~ в(р)Г. '1еек как все в($) — на$'уреь1$ье$$ Ее '!псла, то 1)7 — 1. 'Геореее!а,(!ока)а$(а. Пример ВВТОмага на, рис. 9.1 !!Ока.еывеееч', чтО О1[енку à — 1 В 'Еео[я)м(. Мура В ООНГем с.'!учао у.'Еу $$1$$!Гь ~~ль~я. Здесь, независимо от входного символа а С~(а, ();) = О, дчя 7 = 2, 3,... „7 и (.'(($, ([1) = 1. Рнс. 9.1 ДЕ!~1 того. чтобы отл~~~ть состояния ([,, 1 и <~,, надо перевесте( хотя бы Одно нз них в ()1 (Входным словом длины à — 2) и зат("м подать ( ПГВ один входной символ. Слетовач(:.льно. минимальная д."Еина эксперимента, От:НЕча!О!1!его ($7 1 и (7, равна 7 — 1.

Определение. Пусть 2 автом ага (А, В, ф, ( 1, ГЕ) и (А,В,Щ,С2,Г~) имен)т одинаковые входной и выходной ал([)ав!$$ы. Пусть (г; б ф и (г б «~1. Будем говорить, что зксперимент а (= 4" отличает (.остояния (г„. и ())з если К[1([, д.;) ф Х21а, д„..). Теорема 9.2. Пусть даны, 2 а(гх»г(»мал[(г, ~4( В, Я [, б [ „Г[) с ~.4, В, Я1, « '), Е~). Пус)Х»ь ~ф ~ = », Ц1~ = ю и В [= фс щ Е «~1, Тогда, если д.; и (г. (»Г»»л[зч[г»иь»,. то сущесхг[вует охг)личаьх»111[6 (гх эьсх»а~т.»[((»)гхг», адлины1(([)»+[п1 Доказательство.

Можно ( [итсххь„ч'!'о Щ П Щ =. Рассмотрим автомиг ~А,В,ф« ',Е), в котОРОМ Ц = Я[ [[«~е и Дис)ГРйх[ыа кот01)ОГО получается об'ьедннением диаграмм исходных автоматов. Тогда ~Ц = »+т и по преды)[ущей теор("ме (г,( (гс отличимы зкспериментом а длины Ца)» + н[ — 1. Теорема доказана. Следун)щий пример (рис. 9.2) показыва('х„что оценка г + нг, — 1 в общем случае неулучшаема. Здесь предполагается тг и опять вы- ХОДНОЙ СИМВОЛ Зс[ВИСИТ ТОЛЬКО 0 1' 'ГЕКУЩЕГО ([ОСХОЯНИ51 И НЕ ЗВВИ(..'Ит (ГГ входи(и'о симвог[а. % с»2 [ 1 Рис. 9.2 ..~хегко Видеть, ч'10 е(.'ли не использоВать состо51ние (г втОроГО с)ВТОМатас ТО НЕЛЬЗЯ ОЗЛИ ЧИХЬ СОСТОЯНИЯ ()! И ([1 . ПО")ТОМу СНаЧВЛа НВДО перевести второй автомат словом а[ из д[ в (»' .

При зт()м »1а[)нг — 1 и первый йвтомат под ц('.Йс"1 Вием ([. Иере)йде'Г из (г[ В ф.. зхобы г(а.[[ее ПОЛУЧИТЬ $)аЗЛИЧНЬГЕ ВЫХОДНЫЕ ПОС[[ЕДОВсХХЕЛЬНО(",ТИ, ННДО ПЕ$)ЕВЕСХИ пе$)вь[й автомат из ф. в (~1 и пода.1ь (.Ще Один симвог!. Вс~ГО для 10ГО, [тобы о'![дичи'1ь (»1 ох д1~, потребуется входное слово Д,:[ины 1»»[ — 1) + ~ »" — 1) + 1 = ш + х — 1. Определение. Автомиг„в котором все состояния попарно охличимы, называехся х[1»иведен[(ы.и ([вп»»)А((г~х»»5г[(. Неотгн(чимые состояния и йвтомсх)е Обрйзуьзт клас()ы аквина.т[с н Хиос ги.

Определение. Число классов неотличимых состояний называется весом автомата. Если склеить все неотличимы(." между собой состояния, то диаГраммй корректно перейде'1' В диаг~)ймму приведенного авхомата, ко- ТорЫЙ рвалнзуЕХ то жЕ йвЗОМатно([ ОГОб~)с))КЕНИЕ В~од~~~ СЛОВ В ВЫ- ходные, что и исходный автомат. Рассмотрим следукииу[о задачу. Дан автомат с известной диаграммой, но неизвестно его начальное состояние. Всегда ли существххет вксперимент а, понволяюьций определить что начальное состояние? Последнее равносильно тому, что Г(а,д;) ф Г~а, д ) для лкэбых сосгояний ф ф.

ф. Теорема 9.3. Суи~есгаеуеэээ приведенный автиомага, и коклорви ~<юнэя ~эн1эеделнпгь начал.ьэкэе с~эепхэянне. ДВ7ьнаияэельсгпнО. Рассмот1эиы автомиг на 1эис. 9.3. Здесь пе1эвое число в скобках обозна гает входной символ, а второе — выходной символ. Ф,О1 «1,О Рис. 9,3 Он приведенньэй, так как д2 (этличается от ~Х1 и Ф чкспе1эиментом 1, а ~~$ отличается от дэ чксперименгом О. С другой сторонь~, неч единого акспе1эимента, отличаюгцего все состояния, 'гак как любой зксперимент; начинающийся с О, не отличает д1 и д~, алюбой нксперимент, начинающийся с 1, не отличает д1 н д~.