Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 28
Текст из файла (страница 28)
Система уравнений у(И = Е(х(г), й(~ — 1)), й(1) = О(х(1), И1 — 1)), (1) й(о) = ц., где х(1) е А, у(1) е В, ц(1) е О (1 = 1, 2, ... ) и оо е Я, называется каноническими уравнениями функции (оператора)» с начальным условием йо С помощью диаграмм Мура и канонических уравнений можно задавать и такие детерминированные функции, которые не являются ограниченно-детерминированными. Множество вершин орграфа Г», соответствующего такой д.функции, совпадает с расширенным натуральным рядом Ж = 10, 1, 2,...
). («Орграф» определен в гл. Ч1.) Если»" —.- о.— д. функция, то функции Е(х(1), у(1 — Ц) и С(х(1)., в(1 — 1)) (см. систему (1)) и аргументы, от которых они зависят, принимают конечное число значений. Поэтому возможно табличное задание о.-д. функции» с помощью так называемой канонической глаблицы (табл. 4.1). 128 Гл. 17.
Ограниченно-дегоерминированные функции т аблица 4.1 Вместо канонических уравнений (1) бывает удобно рассматривать такие канонические уравнения, в которых функции выходов и переходов являются функциями й-значной логики Ря (й > 2). Лля получения соответствующего представления функдии 1 алфавиты А, В и С кодируются векторами (наборами), координаты (компоненты) которых принадлежат множеству Еь = (О, 1, ..., й — 1) (й > 2).
Если 1 о.-д. фУнкциЯ и и =) 1ойь )А((, т, =) 1ойь )В([, г =]1ойя )11((, то длЯ кодирования букв из алфавитов А, В и Ц достаточно взять векторы (с координатами, принадлежагцими Еь), имеющие длины и, т н г соответственно*) . Система (1) преобразуется тогда в следующую: уз(1) = Рз(т (1), ", Я, Ч (1 — 1), ", Ч.(1 — 1)): у-(1)=В (' (1) " т Я, Ч1(1 — 1):"., Ч.(1 — 1И; Чз(1) = Сз(тз(1), ..., тлЯ, .Ч1(1 — 1), ..., Ч;(1 — 1И, (2) Че(1) =С„(Х1(1), ..., хиЯ, Ч1(1 — 1), ..., Ч,(1 — 1И, Ч (О) = Ч , " ., Ч.(О) = Чв, Используется также векторная запись систем, аналогичных системе (2).
При такой записи система (2) примет вид у1 д(1) = Г1 1(хоо(1), ц1"1(1 — 1И, с1 (1) = С (х (1) с1 (г 1 И (3) 1~1(О) 1г1 Функции Р, н С, в системе (2) являются, вообще говоря, часптчными, т.е. не всюду определенными. Обычно их доопределяют так, чтобы правые части уравнений в (2) имели по возможности более простой вид. Каноническая таблица, задаю|цел о.-д. функцию у, соответствующую системе (2), имеет по + и+ 2г столбцов и йлл г строк. Уравнения системы (2) называются кононически,ми уравнениями в скалярной форме, а уравнения из системы (1) .-- каноническими уравнениями в векьоорной форме.
л) Если д. функция 1 не является ограниченно-детерминированной, то с=со. у 2. 27иаграммвь гпабяиивь канонические уравнения, схемы 129 М ожно считать, что система (2) определяет функцию из множества Р„'„. Пример 1. Построить диаграмму Мура, каноническую таблицу и канонические уравнения для функции 1'(х)ы = у(1) у(2)... у(1)... (из Рцз ): 0 при 1= 1, ) 1 при 1= 1, 1 при 1>2; ' 11(1) при 1>2; (х(1) при 1 нечетном, в) у(1) = г (У(1 — 1) при 1 четном. Решение. а) Построив три яруса информативного дерева заданной функции (рис. 4.5), видим, что все вершины дерева разбиваются О 1) , О(О),10 0 1 Рис.
4.7 Рис. 4.6 Рис. 4.5 на два класса эквивалентности: первый класс содержит только вершину О, а второй все остальные вершины. Следовательно, вес рассматриваемой функции равен 2, и диаграмму Мура для нее можно построить, отождествляя в «усеченном» дереве, изображенном на рис. 4.6, вершины 1, 2, 3, 4 и «восстанавливая» входные символы, соответствующие ребрам этого дерева. Пиаграмма Мура заданной функции приведена на рис. 4.7. (Вместо двух дуг, идувцих из вершины 0 в вершину 1, мы изобразили на рисунке только одну, приписав ей два выражения; 0(0) и 1(0).
Аналогично мы поступили и с дугами-петлями, исходящими из вершины 1. Начальное состояние помечено звездочкой.) Используя диаграмму Мура, строим таблицу. В качестве «входной» и «выходной» переменных возьмем хз (1) и да(1) (а не х(1) и у(1), Таблица 4.2 чтобы явно подчеркнуть содержательное отличие переменных из первоначального задания рассматриваемой функции от переменных, входящих в ее канонические уравнения).
В качестве переменной 9 Г. П. Гаврилов, А. А. Сапожонка 130 Гл. 17. Ограниченно-детерминированные функции для описания состояний берем О(1 — 1) (на «входс») и О(1) (на «выходе»). Каноническая таблица функции -- табл. 4.2. Из таблицы следует, что уз(1) = О(1 — 1) и д(1) = 1. Значит, канонические уравнения и начальное условие заданной функции таковы: у,® = О(1 — 1), Ч(1) =1 д(0) = О. б) Для нахождения веса функции и построения диаграммы Мура достаточно изобразить три яруса ее информативного дерева (рис. 4.8). 0(0) ЦО) 0(Ц 0 0 ЦЦ Рис.
4.8 Рис. 4.9 Рис. 4.10 Вес функции равен 3. Вершина 0 образует один класс эквивалентности. Второй класс образуют вершины 1, 3, 4, ... Третий класс вершины 2, 5, 6,.... «Усеченное» дерево и диаграмма Мура приведены на рис. 4.9 и рис. 4.10. Построим таблицу. В качестве «входной»переменной возьмем х11), а в качестве «выходной» у11). Для описания состояний берем переменные О~(1 — Ц, дз(1 — 1) (на «входе») и Оз(1), дз(1) (на «выходе»). Состояние 0 кодируем парой (О, 0), т.е. Оз — — пз = О., состояние 1 ко- Таблица 4.3 дируем парой (О, 1), т.
е. д~ — — О, оз — — 1, и состояние 2 . парой (1, 0), т. е. оз = 1, оз = О. Каноническая таблица функции табл. 4.3. В таблице выписаны все наборы значений поременных и1г), а(1 — Ц, дз(1 — 1). Для дз = дз = 1 соответствующего состояния в рассматриваемой диаграмме нет. Из-за етого функции, «описывающие» у11), дз(1) и пз11), являются частичными (не всюду определенными) булевыми функциями.
Мы их доопределим каким-либо образом; например, как в табл. 4.4. 12. Лиаераммвь нгабвииьь канонические уравнения, схемы 131 Таблица 4.4 д (1) у(г) В(1) Чг(г — 1) х(1) де(е — 1) Указанное доопределение дает достаточно простые представления переменных у(1), уг(1) н аг(1) (как булевых функций от переменных х(1), дг(1 — 1) н уг(1 — 1)): у(1) = дг(1 — 1), дг(1) = х(1). уг(1 — 1) и' х(1) е1г(1 — 1), дг(1) = х(1) .е1г(1 — 1) Ч х(1) уг(1 — 1). Тем самым канонические уравнения нами получены.
Остается выписать начальное условие. Оно имеет вид Ог(0) = Ог(0) = О. в) Достаточно построить четыре яруса информативного дерева (рис. 4.11). Все верпгины дерева разбиваются на три класса эквивалентности: первый класс содержит вершины О, 3, 4, 5, 6, ..., второй Рис. 4.11 класс вершины 1, 7, 9, 11, 13, ..., третий класс вершины 2, Я, 10, 12, 14,... Вес рассматриваемой функции равен 3. «Усеченное» дерево и диаграмма Мура изображены на рис.
4.12 ~ф 1 О Рис. 4.13 Рис. 4.12 и рнс. 4.13. Каноническая таблица (с доопределенными значениями соответствующих функций) — - табл. 4.5. Состояния закодированы нами трациционным образом; состоянию 0 сопоставлена пара (О, 0), т.е. аг = аг — — О, состоянию 1 сопоставленапара (О, 1), т.е. Ог =0 и дг =1, состоянию 2 пара (1, 0), т.е.
Ох=1 и аз=О. 132 Гж 1'г'. Ограниченно-дегнерминированные функции Таблица 4.5 Канонические уравнения и начальное условие имеют следующий 'ид УЮ = У11) .0211 — 1) '7х(1) .Ч111 — 1), Ч (1) = Ф) Ч,(~ — 1) Ч,(~ — 1), Чг'1) т(1) Ч1(1 1) Чз(1 Ц Ч, 1О) = Ч, 10) = О. Пример 2. Лля каждой диаграммы, изображенной на рис. 4.14, построить приведенную диаграмму. Решение, а) Рассматривая диаграмму, нетрудно заметить, что вершины 3 и 4 не достижимы из начальной вершины О. Удаляя их, 0(1) ЦО) Ц 0(0) 0(1) ЦО) 0(0) Рис. 4.14 О 10 2 1 0 ЦО) 0 Рис.
4.16 2 Рис. 4.15 Рис. 4.17 получаем диаграмму, изображенную на рис. 4.15. Исходя из этой (новой) диаграммы строим несколько ярусов соответствуюгцего информативного дерева (рис. 4.16; достаточно неполных четырех ярусов). Изображенный фрагмент дерева позволяет сделать заключение у 2. 27иаераммвь гаабяиивь канонические уравнения, схемы 133 2 01 2 2 01 2 ЦО) 0(1) * О 0(1), Ц1) (1:2) 0(1) 0 Рнс. 4.19 Рис. 4.18 Рнс. 4.20 на рис.
4.19 (достаточно трех ярусов). Ясно, что вершины 1 и 2 эквивалентны. Склеивая их, получаем приведенную диаграмму (рис. 4.20). Пример 3. Для частично определеннойфункции 1"(х ): (О, 1)ы — > -в (О, 1)", отображающей заданные последовательности в заданные, построить (еслн это возможно) диаграмму Мура с конечным и по возможности меньшим числом вершин. Затем полученную диаграмму доопределить до диаграммы Мура всюду определенной о.-д. функции нз изР' а) Г(0[ООЦ' ) = 1[0]м И 1(1[100] ) = [ОЦ б) 1([110]ы) = 0[ООЦ и 1(1[10] ) = 00[01Ц .
Решение, а) Так как у заданных входных последовательностей первые символы (т.е. префиксы длины 1) разные, то исходная частично определенная функция может быть продолжена до всюду определенной д. функции, Палее, нетрудно заметить, что заданные входные и выходные последовательности квазипериодические. Значит, исходную частичную функцию можно доопределить до о.-д. функции. (Если приведенные в условии задачи соотношения переписать в виде 1(0[ООЦ' ) = ЦООО]м и у" (1[100100] ') = 0[101010] ', то становится очевидным, что вес подходящей о.-д. функции не больше, об эквивалентности вершин 1 и 2.
Склеивая эти вершины, получаем диаграмму, .представленную на рис. 4.17. Эта диаграмма приведенная, так как обе ее вершины достижимые и не эквивалентны друг другу (хотя бы потому, что дуга, выходящая из вершины 0 и соответствующая входному символу О, помечена выходным символом О, а дуга с таким же входным символом, выходящая из вершины (1, 2), имеет метку 1). Эквивалентность вершин 1 и 2 в диаграмме, изображенной на рис. 4.18, можно обосновать также следующим образом: 1) дуги, соединяющие вершины 1 и 2 между собой, помечены одинаково (на них стоят метки 1(0)); 2) дуги с меткой 0(1), выходящие из этих вершин, заходят в одну и ту же вершину 0; следовательно, вершины 1 и 2 эквивалентны (в силу определения эквивалентных вершин).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
