Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 29
Текст из файла (страница 29)
б) В диаграмме не достижимы вершины 3 и 4. После удаления их получаем диаграмму, изображенную на рис. 4.18. Фрагмент информативного дерева., соответствующего этой (новой) диаграмме, показан 1 134 Гж 1 г'. Ограниченно-детерминированные функции чем 1+ 3+ 6 = 10. Здесь 1 общая длина предпериодов в новой записи всех четырех входных и выходных последовательностей, а 3 и 6 общие длины периодов у последовательностей соответственно из первого и второго соотношений.) Мы вначале не будем пытаться найти диаграмму Мура с минимально возможным (или хотя бы с не очень большим) числом вершин, а просто будем строить какую-нибудь подходящую диаграмму, соответствующую всюду определенной д.
функции, перерабатывающей заданные входные последовательности в заданные выходные последовательности. Для достижения этой цели действуем следующим образом: сначала изобразим часть диаграммы, реализуюшую соотношение 7'[0[ООЦы) = = 1 [0[, а затем добавим к ней часть, отвечающую равенству 7(Ц100[ ) = [ОЦ . Так как соотношение 7"[0[ООЦ") = ЦО[ ' можно записать в виде 7(0[ООЦ ) = ЦООО[", то имеем х[1+31) = х(1) и у[1+ 31) = у[1) при 1 = 2, 3, 4, ... и 1 = 1, 2, ...
Отсюда следует, что данное соотношение можно реализовать 4-вершинной диаграммой с циклом длины 3 [рис. 4.21). Аналогич- 0(0) 10 *01 ф1 0[0)~ 0 1 2 3 Рис. 4.21 0 4 5 6 7 8 д Рис. 4.22 но поступаем со вторым соотношением. Его можно записать так: 7" [Ц100100)"') = 0[101010["'. Следовательно, имеем х0+ бт) = х[ф) и у0+бт)=у0) при 3=2,3,4,... и т=1,2,...,апоэтомурассматриваемое соотношение можно реализовать 7-вершинной диаграммой с циклом длины 6 (рис. 4.22).
Далее «склеиваем» две построенные диаграммы в «начальной» вершине 0 и доопределяем получившуюся при этом «частичную» 0[0) диаграмму подходящим способом до 00 00 диаграммы всюду определенной о.-д. функции. Приходим, например, к диаг)[ 2 рамме, изображенной на рис. 4.23. Эта ЦЮ) диаграмма имеет 10 вершин. ЦО) [ 1[1) 1 1) Де пр р 0(0) Ц О[1) связи между входными и выходными д 6 последовательностями, указанными в 1[1) условии задачи, и учтя структурные особенности этих последовательнос- 5 0[0) 6 О[1) 7 тей, можно построить более «экономную» [по числу вершин) диаграмму, реализующую заданное частичное отображение.
1 0[1 1(1) 1(1) 0[0) Рис. 4.23 у 2. Ливграммвп хнабяиивн канонические уравнения, схемы 135 3 О 10) 1[1) Цо) По) Рис. 4.24 На рис. 4.24 приведены три 5-вершинные (а- в) и одна (г) 6-вершинная диаграммы, реализующие заданную частично определенную функцию. б) Входные последовательности можно записать так: [110]" = = 1101[10Ц" и 1[10]ы = 110ЦОЦ"'. Отсюда следует, что их префиксы длины 4 совпадают [а соответствующие префиксы большей длины попарно отличны друг от друга). Значит, прежде чем строить диаграмму, надо проверить, совпадают ли префиксы длины 4 у заданных выходных последовательностей [если эти префиксы различные, то не будет выполняться условие детерминированности). Запишем заданные выходные, последовательности в иной форме: 0[ООЦ" = 0001[ООЦы и 00[01Ц" = 0001[10Ц . Теперь очевидно, что у этих последовательностей префиксы длины 4 одинаковые.
Соотношения Д[1101[10Цы) = ОООЦООЦ ' можно реализовать диаграммой, имеющей только две вер- 1 0) шины [рис. 4.25). Однако 10) «расширить» эту диаграм- О 1 О О[О) Ц1) му таким образом, что- " О(О) 1 2 бы реализовывалось и со- ЦО) ЦО) отношение 1(1101[ОЦ~) = Рнс. 4.25 Рис. 4.26 = 0001[10Ц"'', не удается. Поэтому для получения возможности одновременной [совместной) реализации обоих соотношений надо более гибко строить части иско- 136 Гж 11'.
Ограниченно-детерминированные функции мой диаграммы, помня о том, что предстоит «склеивать» их. В нашем случае каждая из двух частей диаграммы должна иметь одинаковое «начало», соответствующее общему префиксу (длины 4) двух заданных входных последовательностей. (Кроме того, полезно принять во внимание, что общее наименьшее кратное длин периодов заданных входных и выходных последовательностей равно 6.) Подходящая диаграмма для соотношения 1" (110Ц10Ц") = ОООЦООЦ" изображена на рис. 4.26. Диаграмма, реализующая соотношение 1(110ЦОЦ ) = ОООЦ10Ц' и приспособленная для склейки с предыдущей диаграммой, изображена на рис. 4.27.
При ее построении использовался, как обычно, «полный перебор» возможных случаев. Покажем подробнее, как это делалось. До вершины 2 диаграмма совпадает с предыдущей и реализует преобразование ЦО) ЦО) ЦО) ЦО) (0) ЦО) Рис. 4.28 Рис. 4.27 префикса 1101 в префикс 0001 (дуга (1, 0), изображенная на рисунке штриховой линией, для реализации соотношения 1"(110ЦОЦ' ) = = ОООЦ10Ц не нужна, но се следует учитывать при построении диаграммы). Далее выясняем, можно ли «направить» дугу из вершины 2 с нужной нам меткой 0(1) в какую-либо из имея>шихся вершин О, 1 или 2.
Если эта дуга будет входить в вершину О, то слово 010 будет преобразовываться в слово 100 (при «движснии» по диаграмме из вершины 2), а нам нужно иметь слово 101. Следовательно, в вершину 0 эту дугу направить нельзя. Не может заходить рассматриваемая дуга и в веригину 1, так как иначе слово 01 преобразовалось бы в слово 11 (а мы должны иметь слово 10). Делать эту дугу петлей в вершине 2 также нельзя, ибо в противном случае имеем следующее: слово 010 преобразуется в слово 100 (а нам нужно слово 101). Итак, дуга, выходящая из вершины 2 и имеющая метку 0(1), должна заходить в «новую» пер~пину 3. Далее смотрим, куда можно направить дугу из вершины 3 с меткой 1(0).
Легко убеждаемся в том, что ни в одну из вершин О, 1 или 2 эту дугу вести нельзя, но сделать ее петлей в вершине 3 можно. Затем выясняем, куда можно направить дугу из вершины 3 с меткой 0(1). Оказывается, что для этой дуги нужна новая вершина 4. Наконец, нетрудно проверить, что дугу с меткой 1(1), выходящую из вершины 4, можно направить в вершину О. После «склеивания» двух построенных диаграмм в вершинах О, и 2 остается подходящим способом доопределить получившуюся «частичную» диаграмму до диаграммы всюду определенной функции.
На рис. 4.28 изображена одна из таких диаграмм. 22. 27иаераммвь нгабяиивь канонические уравнения, схемы 137 Пример 4. Найти вес о.-д. функции 7' из Рг', заданной канонип1 ческими уравнениями: Ы1) = Ф1). Чг(1 — 1) Ог(1) = И) - Ч И вЂ” 1) Ог(1) = уг(4 — 1) Е уг(1 — 1) а,(0) = 1, аг(0) = О. Решение.
Эту задачу можно решать путем построения инфор- мативного дерева функции 7. Однако мы поступим иначе: сначала Таблица 4.6 построим для функции 7" каноническую таблицу, затем по таблице построим диаграмму Мура и, наконец, получим из нее приведенную диаграмму. Число вершин в приведенной диаграмме равно весу функции 1 (см. задачу 2.3.3). Каноническая таблица функции 7" табл. 4.6. Пиаграмма Мура функции 7" изображена на рис. 4.29. Анализируя ее, получаем; состояние 00 эквивалентно состоянию 01, а состоя- ЦО) ние 10 состоянию 11. Поэтому приведенная диаграмма выглядит так, как показано на рис. 4.30. 0(Ц Рис. 4.30 Рис.
4.29 Следовательно, вес функции 2" равен 2. Нетрудно видеть, что переменная аг является фиктивной; функция 7 эквивалентна (по своему функционированию) функции следующей 7", задаваемой каноническими уравнениями и начальным условием: у(е) = х(е) 0(4 — 1), 0(1) = х(е) д(4 — 1), а(0) = 1. Вес функции ~' равен 2.
138 Гл. Ге'. Ограниченно-деенериинированные функции 2.1. Построить диаграмму Мура, каноническую таблицу и канони 2)... д(1)... из Ря'ол.. ч еские уравнения для функции 1(х' ) = д(1) д( 1 при 1=1, х(1 — 1) е х(е) при 1 > 2; ® О при 1=1, , (1 — 1) — ед(й — 1) при А>2; д д ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ | ~ ~ | ~ ! 3) д(г) = д(й — 1).
х(е) при Ь > 2; 1 при 1=1, 2, хЯ -в х(2) при 1 > 3; 4 д 1 ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ | | ~~ !~ х(1) при С = 1, 5) д(г) = х(1 — 1) ~3 х(1) при 1 > 2; (х(1) при 1 = 1, 2, 6) д(Ц = ~х(1 — 1) при 1 > 3; х(2), если 1= 2, 7) дФ= 1 в остальных случаях: (х(1) -+ х(1), если 1 = 1, 2, 3, 8)дф= ~ О в ином случае; х(1) при 1 = 1, О)дФ= д(1 — 1) ч' х(е) при 1 > 2; < х(1), если 1= 1, 2, 1О) д(1) = д(1 — 2) Юд(1 — Ц, если 1> 3; ~ 11)д®= ' * О, если 1=1 и 1=3, х(1), если 1 = 2 или 1 > 4; 12) дф = х(1) при 1 = 1, д11 — 1).
х(1) при 1 > 2: á 13) д(1) = 1 при 1=1, х(1 — 1) Ч х(1) при 1 > 2; 14) д(1) = х(1) при Х = 1, д(1 — 1) Ю х(1) при 1 > 2; á у" 2. Лиаграммьь хаайяииьь нанвнинееиие уравнения, схемы 139 ( х(х), если 1 нечетное, 15) у[1) = [ О, если 1 четное; т(х), если 1 нечетное, 10) у[1) = у[1 — 1) Юх(1), если 1 четное: х[х), если 1 нечетное 17) у(1) = < х(1) — > у(1 — 1), если 1 четное; 18) 1(ты) = Ох(2) [1]; 19) ~(х~) = т(1) х(2) [0]~; 20) Х[т5ы) = Ох(1) [01]'; 21) ~[ты) = [х(1) О]"'; 0"', если хы = 0', 22) Х[т' ) = 0' [1]'", если х ' = 0'1х(1+ 2) т(1-р 3)...
и 1 > 1 1"', если х = 1т(2) х[3)...; если хы = 0 ' или х' = 1', 23) х (х") = 1' [0]~,. если х~ = О'1х(1+ 2) х(1+ 3)... или т~ = 1'От[1+ 2) х[1+3)..., где 1 > 1; 24) у(1) есть 1-я цифра после запятой в двоичном разложении числа 5/7; 25) у[1) есть (1+ 1)-я цифра после запятой в двоичном разложении числа 1/9; 26) уф есть (1+ 2)-я цифра после запятой в двоичном разложении числа 11/15; 27) у(1) есть [х+ 1)-я цифра после запятой в двоичном разложении числа х[1)/5; 28) у[1) есть [1+ 2)-я цифра после запятой в двоичном разложении числа Зх[1) /7; 29) у(1) есть |-я цифра после запятой в двоичном разложении чис- ла (х[1) + 1)/3; е ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ ~ ~ ! ~ ~ ~ ~ ~~ | т(1) при 1 = 1, 30) у(1) = х[1) х(2) при 1 = 2, [у(1 — 2) ах[1)) х(1 — 1) при 1 > 3; т(1) при 1 = 1, 31) у(1) = х[1) + х[2) при 1 = 2, х(1 — 2) Ех[1 — 1) Ет[1) при 1> 3; 140 Го.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
