12. Схемы из функциональных элементов с элементами задержки (СФЭз), автоматность осуществляемых ими отображений. Реализация КАВ СФЭз (1107932)
Текст из файла
Лекция: Схемы из функциональных элементов сзадержками (СФЭЗ), автоматностьосуществляемых ими отображений.Представление КАВ СФЭЗ. Упрощения КАВ.Отличимость и неотличимость состояний КАВ.Теорема Мура о длине слова, отличающего дваотличимых состояния КАВ.Лектор - доцент Селезнева Светлана НиколаевнаЛекции по “Дискретной математике”-2,1-й курс, группа 141,факультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mathcyb.cs.msu.suСФЭЗУпрощение КАВСФЭ с задержкамиСхемой из функциональных элементов с задержками(СФЭЗ) S(x1 (t), . . .
, xn (t); y1 (t), . . . , ym (t)) в базисе {&, ∨, ¬}называется1) ориентированный граф G = (V , E ) с возможнымиориентированными циклами, все вершины которого имеютполустепень захода не больше двух;2) вершины с нулевой полустепенью захода называютсявходными и им приписываются входные переменныеx1 (t), . . . , xn (t);3) некоторым вершинам с полустепенью захода, равнойединице, приписывается элемент единичной задержки z,причем в любом ориентированном цикле графа G должна бытьхотя бы одна вершина с приписанным элементом единичнойзадержки;СФЭЗУпрощение КАВСФЭ с задержками4) остальным вершинам с полустепью захода, равной единице,приписываются элементы отрицания ¬;5) каждой вершине с полустепью захода, равной двум,приписывается или элемент конъюнкции &, или элементдизъюнкции ∨;6) некоторые (в том числе и входные) вершины называютсявыходными и им приписываются (различные) выходныепеременные y1 (t), .
. . , ym (t).СФЭЗУпрощение КАВТеорема о функционировании СФЭЗТеорема 1. Каждая СФЭЗ S(x1 (t), . . . , xn (t); y1 (t), . . . , ym (t))осуществляет автоматное отображение входовx1 (t), . . . , xn (t) в выходы y1 (t), . . . , ym (t).Доказательство. Рассмотрим граф G = (V , E ) СФЭЗ S.Пусть v1 , . . . , vk ∈ V – все вершины, которым приписанэлемент единичной задержки z. Рассмотрим вершину vi , в неевходит одна дуга из вершины, которую обозначим vi0 .
Удалимэту дугу из графа. Вершине vi0 припишем новую выходнуюпеременную qi (t). Вершина vi станет входной, ей припишемновую входную переменную pi (t). Заметим, что т.к. в любомориентированном цикле графа G хотя бы одной вершине былприписан элемент z, выполнив такое преобразование длявершин v1 , . . . , vk , мы разорвем все ориентированные циклы.СФЭЗУпрощение КАВТеорема о функционировании СФЭЗДоказательство (продолжение).
В результате получили СФЭЗ(без задержек) S 0 . Запишем функции алгебры логики, которыереализуются в ее выходах:yj (t) = Fj (x1 (t), . . . , xn (t), p1 (t), . . . , pk (t)), 1 ≤ j ≤ m;qi (t) = Gi (x1 (t), . . . , xn (t), p1 (t), . . . , pk (t)), 1 ≤ i ≤ k.Из описания функции единичной задержки верно, чтоpi (t) = qi (t − 1), qi (0) = 0. Поэтому yj (t) = Fj (x1 (t), . . . , xn (t), q1 (t − 1), . .
. , qk (t − 1)), 1 ≤ j ≤ m;q (t) = Gi (x1 (t), . . . , xn (t), q1 (t − 1), . . . , qk (t − 1)), iqi (0) = 0,1 ≤ i ≤ k.Т.е. построили канонические уравнения. А значит,преобразование – автоматное.СФЭЗУпрощение КАВТеорема о представлении КАВ СФЭЗТеорема 2. Каждый КАВ A = (A, B, Q, ϕ, ψ, q∗ ) может бытьреализован схемой с задержками в базисе {&, ∨, ¬} принекотором кодировании элементов из множеств A, B, Qвекторами из нулей и единиц.Доказательство. Пусть |A| = r , |B| = s, |Q| = t.Закодируем элементы множества A векторами(x1 , x2 , .
. . , xn ) ∈ {0, 1}n , где n = dlog2 r e;элементы множества B – векторами (y1 , y2 , . . . , ym ) ∈ {0, 1}m ,где m = dlog2 se;элементы множества Q – векторами (q1 , q2 , . . . , qk ) ∈ {0, 1}k ,где k = dlog2 te, причем начальное состояние q∗ закодируемнулевым вектором (0, . .
. , 0).СФЭЗУпрощение КАВТеорема о представлении КАВ СФЭЗДоказательство (продолжение). КАВ A можно задатьканоническими уравнениями: y (t) = ϕ(x(t), q(t − 1));q(t) = ψ(x(t), q(t − 1));q(0) = q∗ .Перепишем эти уравнения для кодов элементов множествA, B, Q. При этом функции ϕ и ψ преобразуются в векторыфункций алгебры логики (F1 , . . . , Fm ) и (G1 , . . . , Gk ): yj (t) = Fj (x1 (t), . . . , xn (t), q1 (t − 1), .
. . , qk (t − 1)), 1 ≤ j ≤ m;q (t) = Gi (x1 (t), . . . , xn (t), q1 (t − 1), . . . , qk (t − 1)), iqi (0) = 0,1 ≤ i ≤ k.(1)СФЭЗУпрощение КАВТеорема о представлении КАВ СФЭЗДоказательство (продолжение). Теперь построим СФЭ (беззадержек) S 0 в базисе {&, ∨, ¬}, реализующую на выходахy1 (t), . . . , ym (t), q1 (t), . . . , qk (t) функции алгебры логики:yj (t) = Fj (x1 (t), . . . , xn (t), q1 (t − 1), . . . , qk (t − 1)), 1 ≤ j ≤ m;qi (t) = Gi (x1 (t), . . .
, xn (t), q1 (t − 1), . . . , qk (t − 1)), 1 ≤ i ≤ k.После чего соединим в схеме S 0 выход qi (t) со входомqi (t − 1) через элемент единичной задержки z для всехi = 1, . . . , k.Получим СФЭЗ S, осуществляющую автоматное отображение всоответствии с каноническими уравнениями (1).СФЭЗУпрощение КАВФункции ϕ̄ и ψ̄Пусть A = (A, B, Q, ϕ, ψ, q1 ) – КАВ.Определим по функциям ϕ и ψоднозначные функции ϕ̄ : A∗ × Q → B ∗ и ψ̄ : A∗ × Q → Q.Для всех a ∈ A, α = ai1 ai2 . . . aik ∈ A∗ и q ∈ Q положим:ϕ̄(a, q) = ϕ(a, q);ϕ̄(ai1 ai2 . .
. aik , q) = ϕ(ai1 , q)ϕ̄(ai2 . . . aik , ψ(ai1 , q));ψ̄(a, q) = ψ(a, q);ψ̄(ai1 ai2 . . . aik , q) = ψ̄(ai2 . . . aik , ψ(ai1 , q)).СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 .
. . aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1qai2...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26q...aikα = ai1 ai2 . .
. aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗6bi1 = ϕ(ai1 , q)qСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗6bi1 = ϕ(ai1 , q)q?bi1СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . .
. aik ∈ A∗6bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)q?bi1СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗6-q?bi1qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...aikα = ai1 ai2 . .
. aik ∈ A∗6-q?bi1qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...aikα = ai1 ai2 . . . aik ∈ A∗6-q?bi1qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . .
. aik ∈ A∗6-q?bi1aik?bi2qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗6-q?bi1aik?bi2qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗6bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )- -q?bi1aik?bi2qi2qi3СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 .
. . aik ∈ A∗6- - ...q?bi1aik?bi2...qi2qi3. . .bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...66- - ...q?bi1α = ai1 ai2 . . . aik ∈ A∗aik?bi2...qi2qi3. . . qikbi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...66- - ...q?bi1α = ai1 ai2 . .
. aik ∈ A∗aik?bi2...qi2qi3. . . qikbi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗aik66bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )- - ...q?bi1??bi2...bikqi2qi3. . . qikСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . .
aik ∈ A∗aik66bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )qik+1 = ψ(aik , qik )- - ...q?bi1??bi2...bikqi2qi3. . . qikСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 .
. . aik ∈ A∗aik66- - ...-q?bi1?bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )qik+1 = ψ(aik , qik )?bi2...bikqi2qi3. . . qikqik+1 = ψ̄(α, q)СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗aik66- - ...-q?bi1?bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )qik+1 = ψ(aik , qik )?bi2...bikqi2qi3. .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
