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

Х.~р,„) = 2 2" + 012"1 ~). Д(йс(вительно, тРебУемаЯ в((1»хнЯЯ ОЦенка Д(Я ЦРа) вытекает из Еео1»емы «.2 ~см. следствие), а, '1ак как БП е(О.... „(1»~ 1 (»61»е»зу1(»1 незабиваемое множество БП 11„, то теорема 7.3 даст необходимую нижеиок» оценку. "Подстановка констант вместо некоторых входных переменных (.'ФЭ подразумевает, что "константные' входы схемы, а также т(" элек(енты, на входах которых вона:,(кент((в кон«так(ы, пос;(едоаапе:Еъно уст1»ае(н(отса прнмененнем гож»(е(.та О 1, 1 =О.

т-О=О. ХЧ1=1. »' 1=хЧО=хдотех пор, (кЕкаэто возможно. Рассыогрим. в зак»иочение» воп1)ос о сложносз и реалнзации симме1рических ФАЛ. Функция Дх!»... » х„) называется симме)>)р((веско(1, если ее знач()ние не меняется при лн>бой перестановке аргументов. Значение симметрической ФАЛ однозначно определяется числом единиц в наборе значений (.'.е пер(.'.менных, так как дв(1 набор(1 с ОдннакОВым '(н(>л(2м единиц всегда можно получить друг из друга некоторой перестановкой аргументов. Заметим„что любая отличная от константы симметрическая ФАЛ Д(х!»...

»х„) является существенной ФАЛ, и позтому Ц!) н — 1 со(е)асно лемме 7.3. Теорема 7.5. Любую с(иим(вт)р((нес)(ую ФАЛ от п неременных можно реихизо()ать со ело>(сносгнью 9и + О ~ —" ( !ока ) До)>азательс)г)((о. Пус:гь ~(х!... х„,) — симметрическая ФАЛ, Й =)1О$1~11+1)~) а ФАЛ д(у(....,у!) н(1 набО!)е О = ~(>!»...,(1~),!де ~Й~ )(„равна значеннк) ФАЛ ~ нв, наборах с ~о~ единнцами и Н1)!(нимь(ет н~)оизво>!ьн ь((».

зна»)ен1(я на Оста.'! ьных набо1)зх. Пусть» счетчнк с входными переменными х!»...,х„(см. замечание к теореме 6.3) сложности не более, чеы 9~11+Й""'), а Е" — СФЭ» реализукицая ФАЛ д и имеющая сложность не более. чем 6~1+о~1)) — ~см. теорему 7.1). Схема ь Еу» которая получается ирисоеднненнем выходов СФЭ К' к входам СФ )»»" » 1)(»ализует» Очевндно, ФАЛ !» н ТеО1>ема дОказана. 'Часть 3. Автоматы ~ 8.

Автоматные функпии. Их реализапия схемами из функпиональных элементов и элементов задержки =. (й) = Г(х(й), ц(1 — 1) ) д(й) = С(х(г), ц(1 — 1)) д(0) = цо (8.1) Эти равенства называются каноническими уравнениями автомжга. Легко видеть, что из канонических уравнений по х(1) и д(0) = ао однозначно определяются -(1) и д(1). Затем по а(1) и х(2) однозначно определяются (2) и а(2) и тд. В резульгжте по входной последовательности х(1), х(2) „..., х(ьз) однозначно определяется выходная последовательность -,(1), ~(2),..., (ьз), то есть автомат осуществляет отображение последовжгельностей любой длины (конечной или бес- В данном параграфе рассматриваются некоторые вопросы, связанные с автомагами и осуществляемыми ими отображениями. Подробное изложение теории автоматов можно найти в (?) .

В (?) рассмжгриваются автомжгные отображенияия и операции над ними. Здесь злы рассмотрим связь между автомжгными отображениями и схемами из функциональных элементов и элементов задержки. Определение. Иниииальным автоматом называется любая шестерка (А, В, Я, С, Е, до), где А, В, Я вЂ” произвольные множества, С функция, отображающая пары из декартова произведения А х Я в Я, Р— функция, отображающая пары из А х Я в В, и ао Е Я. Множества А, В, Я называнися, соответственно, входным алфавитом, выходным алфавитом и алфавитом (мно:нсеством) состояний.. Функция С называется функцией ьзереходов., функция Р функцией выхода., ао называется начальным состоянием.

Определим функционирование автомжга. Буцем рассмжгривать параметр 1, принимающий значения 0„1,2,..., который можно интерпретировать как дискретное время. Будем считать, что на вход автомжга может поступить любая последовжгельность а(1), а(2), а(3),...

(конечная или бесконечная), где а(1) Е А для всех 1. Введем переменные ц(1), 1 = 0,1,... и ®, 1 = 1,2,..., которые будем называть состоянием автомата в момента 1 и выходным зна гением в момент 1. Пусть х(г) значение входа в момент Й. Тогда определилл (8) и д(Й) равенствами кОнечнОй) с клементами из А в последонатеэ!Ьно((ти тОй же длины с Элементами из В.

Определение. Пусть А и  — два множества. Огображс.ние по«. И)довес)ельне(т('й с злементвмн 1!з,4 в посэн донате !ьгнн::)и с з.:!ем(!Г)ами из В называется с)н)ном(11))но(1 фунь«11!(е(1) если сущестнуег инициальный автомат. Осу!Цес!Вля!Ощий зто отооражение. Пример. Пусть '1 = В = Я = 10,11 и анчомат описывается ('ледующими канОниче('кими уран н(.'ниями Легко видеть. что нходная последонательность (111), а12), (113)„...

отображает((я такими! автомагом в последовигельность О„а11)„а~2),.... 3тот автомаг называется едиьги (ио!1 заде1);))«ко(1,. Автоматы удобно задан)ггь геометрически с помощью ориентированных !1)афон. П1)и зтом каждому с(эсгоэ!Иию из множес-1на О «ОНО«Гав::!Яет('Я ве1эшина (эРГ1эафа„и кажДОй па1)е 1(1, ч). 1Д(! «1 (- А! д 1= Я «ОНО«1знэ!яегся д1 га„ид~ щая из в()ршины, соогве!()Твующей (1, н вершину, соотнечэгтнующук) С1а, д). 3!Ой;.~уге приписывается пометка (а, Г1(!.,д)). Вершина, соответствукнцая начальному состоянию д()) помечается 1мы будем помечагь ее звездочкой).

Описанный гра(1) с пометками называется диаграммой Мура заданного ав!Омага. Например, на рис. 3.1 представлена диаграмма Мура для задержки. ~.) Рис. 8.1 Л. ко д, ь, д -р ..Му1' дн:н' д По дугам и пометкам на, дугах однозначно определяются функции переходов и Выхода. Рас«могрим теперь клас(. «хем, с помощью кОторых можно реализОВК1 ь автомагные ())ункции.

Определение. Пусть задан базис Б=1(с1,..., Е, Л1, где о 1,.... Г, — функциональные нлементы 1«м. параграф 4), а Рс — злемент единичной зад(".ржкн, имен)щий один вход и один выход, Схемой из функциОнальных злементОВ и зчемснгОВ зе)де1)жки ~СФ33) в оазисе Б называется граф, который удовлетворяет пунктам 1)-3) опреде:,!ения СФЭ (см. стр.?) и в котором любой ориентированный цикл проходит хотя бы через одну вершину, соответствующую элементу задержки. Будем считать, что все переменные СФЭЗ принимают значения из множества (О, 1~ и могут менять их в моменты времени Р = 1,2,....

При этом функпионирование элемента Л описывается уравнениями (8.2), а функционирование ФЭ Е;, имеющего й; входов, по-прежнему описывается ФАЛ у;(и~,..., и~„.), ~ = 1,..., я. Для описания функционирования СФЭЗ с г элементами задержки Л поступим следующим образом. Пусть г-я задержка Л;, г = 1,....г, приписана вершине е;, в которую идет дуга из вершины и~;.

Для всех ~ = 1,..., г удалим из СФЭЗ дуги (ж;, ю;). По определению СФЭЗ в полученном после этого графе не будет ориентированных циклов и он, тем самым, будет представлять собой СФЭ. Входами этой СФЭ будут все входы исходной схемы, а также все вершины в,, г = 1,..., г (заметим, что все они различны и отличны от входов исходной схемы). Выходами полученной СФЭ об ьявим все выходы исходной схемы и вершины и~;„с = 1,..., г.

Пусть в исходной схеме выходам приписаны переменные "~,..., ",„., входам переменные х~,.... х„. Вершинам ю; припишем переменные д~~,..., д'„, а вершинам и; переменные д~,..., у„. В соответствии с определением функционирования СФЭ, для некоторых ФАЛ ~;, у справедливо: (8.3) Естественно считать, что равенства (8.3) выполняются в каждый момент времени 1 = 1, 2, 3,..., то есть ; ф = Ях~(~),..., х, ®, д', ф,..., д„'(й) ), к = 1,..., т цЯ = д1(тЯ....., т„(~), д~~(Е),...., д',®), ) = 1,..., г.

Так как. в соответствии с каноническими уравнениями (8.2), выход элемента задержки в момент 1 совпадает с его входом в момент 1— 1, то естественно считать, что в исходной схеме д;'® = О;(1 — 1) при Р = 1,2,... для всех ~' = 1,..., г, где д;(О) = О. Тогда равенства (8.4) принимают вид (где г = 1... п~ и 1' = 1,..., г): (8.5) Полученные равенства определяют функционирование СФЭЗ и называются ее каноническими уравнениями. Пример. СФЗ . ~' на рис. 4.4б янля((тся я«1ейкой суммаго11а и реализует ФА,:1 =! — — хч (l тд' ~/ уд'. =2 — — х:,„'', !! ',: у~'. Тогда схема на рнс.

8.2 будет иметь канонические ураннения Если на входы 2: и !1 этой СФЭ3 подавать дна двоичных числа по одному разряду В каждый момент Времени, начиная с ыла«1п(их разрядон, тО на ВыхОде сх((мы б«де1 Быде(нж( ься стымее этих чисел, не1«1иная с м.'1«1дн1их разрядОВ- 3'Га схема назынается Г!Ослед(1((ЙГГ!е;4ье(ым с(~(.м ма" тира,м. Рис. 8.2 Пусть Е~ — множество Всех набороВ длины п с элементами О и 1. Если зе(дана последоинтельн(н"Гь наборон из.Е2 В каче('тне значений входных переменных х;(~), ! = 1,...,п, Е = 1.2,..., то согласно (8.5) НО ним Оде!Означно О!Гределяется ИОс недо Ве(1 ель нОс 1 ь нзборОВ длины НГ =!(Г),... «,„(Г) для Г = 1., Таким образом, схема осуществляет Н11(«обр(ГЗОВание по(!Ледояа(ез(ьнОс'Гей с (1лементами иэ Е2 В пос2!едонагельности с элементами из .Е',"'.

Определение. Пусть антоматная функция 2 отображает последОВж1'ельнОсз'и В кОнече1Ом злфани'Ге А Б 11О(.'л((дОБНГельнОсти Б конечном алфаните В. Пусть СФЭЗ К ос~:ществляет преобразонание с! Носледоаательностей (. элементами из .Е~ в последоваг(льности с э.:!еме(ггами из Ц~. Будем гоноригь, что Х моделируе(Г1 (,-, если сущестнуеот отображения (ьод(121о(!Онил) Х11 ..4 -+ .Е~~ и ХТ2 .  — ? Е.',"'. сопос(ниляипцие разе(ым алеман!еам разные э.:Еем(н'Гы и Об.(аданнцие свой(.ГВОм: для ле()бой последона(ельности Т = а(1)а(2)...

ВФ Б ал- фаните А„если (Р) = Х(. = 6(1)6( )... 6(~)„то ~ '(К!(Р)) = Х~2(Т), где Х~ !(Р) = Х~!(Г((1))Хъ. !(а(2))... Х~1(аф)„ Х12(т) = Х12(6(1))К2(6(2)) ° - - Х(2(6(Г)). Теорема 8.1. 1) ОГГ!Обр((лсение. ос(1щес(пвллемое леоба(! СФ33, я((ляетсе( ивтоА(агг!н«о(2 функ(11(е!(. 2) Длм, леобо(2 (2((п(омитноО функ(рт еуп~еепиует моделиЕчуюлчая ее СФЗЗ 6 базисе из функциональных элементпов дизвюнк~ии, конвюнкйии, огприианил и элеменгпи задерзкки. Доказатпельегпби. 1) Пусть отображение ~~, осуществляемое схемой Е., задается каноническими уравнениями (8.5). Введем переменные Х = (т1,..., х„), Я = (д1,..., д„)., Я = (~л,..., -„,), принимающие значения, соответственно в Е2', Е2, Е~". Положим д0 = (О,..., 0).

Тогда (8.5) можно переписать в виде где функции Г, С не зависят явно от ~. Отсюда видно, что отображение, осуществляемое схемой, совпадает с отображением, задаваемым автоматом (Е~, Е~™, Е~, С, Г, д0), то есть является автоматной функцией. 2) Пусть автомагная функция дана автоматом .0 (А, В, © С, Р, д0). Выберем и, гп, г так, что 2" /А), 2 /В), 2" /Я/. Рассмотрим произвольные отображения (кодирования) К~ . А — + Е~, Ег~ . 'В -+ Е~, Кв . Я -+ Е~', при которых разные элементы отображаются в разные элементы.