Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 24
Текст из файла (страница 24)
Таким образом, 3-й символ выходного слова, соответствующий входному слову 010 х(4) х(5)..., зависит не только от первых трех букв этого слова, но также и от символов х(4) и х(5). Значит, рассматриваемое отображение не является детерминированным. (Заметим, что у(1) = х(1) и у(2) является однозначной функцией символов х(1) и х(2).) Пример 6. Через 8 обозначим здесь подмножество всех таких слов х' из множества (О, Ц ., в которых на четных местах стоят единицы, т.е. х(2в) = 1 при в > 1.
Выяснить, можно ли функцию 1" доопределить до детерминированной: [1х, если х 68, (1, если х = 01[0] х", если х Е 8., б) У(хч ) = 0", если х ' =00х(3)х(4)... х(1)... (т.е. входное слово начинаотся с двух нулей). Решение. а) Очевидно, что значение первого выходного символа у(1) не зависит от входного символа (у(1) = 1 и при хм = 01 [0]"', и при х Е 8). Однако у(2) является функцией от последовательности х(2) х(4) ... х(2в) ..., причем у(2) = х(1), если х(2в) = 1 при всяком в > 1, и у(2) = 1, если х"' = 01 [11]м. Рассмотрим два входных слова: [01]" и 01 [0]".
Имеем 1([01]") = = [10] ' и Д(01 [0]'') = 1 . Значит, у(2) = О, если хн = [01], и у(2) = 1, если хм = 01 [0] ', т.е. у(2) не является однозначной функцией от входных символов х(1) и х(2). 108 Гл. Ре'. Ограниченно-дегпернинированные функции Таким образом, рассматриваемая нами функция 7' не может быть «продолжена» до детерминированной (она уже сама недетерминиро- ванная, хотя и не является всюду определенной на множестве (О, Ц ). б) Из приведенного описания функции у видно, что у(1) = х(1) и у(2) = х(2) как для х Е 8, так и для хы = ООх(3) х(4) ...
х(1) ... Далее, если х(2) в рассматриваемых входных словах равно О, то у(1) = 0 при всяком 1 > 3, а если х(2) = 1, то д(1) = х(1), 1 > 3. Зна- чит, заданную функцию ( можно попытаться доопределить следующим образом; если х = х(1)1х(3)1х(5)1... 1х(2в — 1)Ох(2в+ 1)х(2в+ 2)..., где в ) 1, то ((х ) = х(1) 1х(3) 1 ... 1х(2в — 1) <0) (другими слова- ми, на «выходе» выдается д(1) = х(1) до тех пор, пока при некотором 1о = 2в на «вход» не поступит символ 0; после этого у(1) = 0 для всех 1 > 1о. Очевидно, что у (хй ) - - д.
функция, являющаяся продолжением функции 1 (х '" ) . 11ри мер 7. Выяснить, является ли функция У(ххн ) = у(1) у(2)... ... у(1)... (из Р, ',) о.-д. функцией, и найти се вес: цз ') у%= х(1) при 1= 1, 2, х(<1/3<) при е ) 3; (1) 0 при в=1, х(т) — в у(1 — 1) при Г > 2; у 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ | ~ ~ ~ ~ | <(1, если 1 --.
нечетное число, в) у(1) = (х(1), если 1 четное число. Решение. а) Из приведенного описания функции 7 (х н ) следует, что для получения выходного символа при 1 = Зв (в > 1) необходимо «хранить в памяти» входной символ, поступивший в момент време- ни в, т. с. этот входной символ надо «помнить» в течение 2в моментов времени.
Значит, для «реализации» рассматриваемой д. функции нужно иметь бесконечную (растущу|о во времени) память, что соот- ветствует бесконечному множеству состояний. К такому же выводу можно прийти, строя для заданной функции фрагменты ео информативного дорева. (Однако потребуется постро- ить 8.
9 ярусов дерева, что весьма громоздко.) Для обоснования того, что данная функция не является ограни- ченно-детерминированной, рассмотрим остаточные функции, порож- денные словами 0' = 00... О, где в > 1, и сравним значения этих в рвв функций на входном слове 1 '. Имеем у (О' 1ы) = 00... 0 <1< ', а следоЗв-~-2 вательно, 15,(1 ) = 00 ... 0 <1] . Значит, для разных значений в эти зв»2 функции попарно не эквивалентны. Таким образом, вес функции у' равен со, т.е. она не является о.-д. функцией.
3 б Отображения последовательностей б) Построив четыре яруса информативного дерева заданной функции (рис. 4.3), нетрудно высказать предположение, что все вершины Рис. 4.3 дерева разбиваются на три класса эквивалентности: первый класс содержит только вершину О, второй -- вершины 1, 2, 4, 6, 10, 14 и т.д., а третий --. вершины 3., 5, 7, 8., 9, 11, 12, 13 и т.д.
Вершинам из второго класса соответствуют остаточные функции )е(хн), Де-,(х") и др(хн), где е > 1., а вершинам из третьего класса остаточные функции (;. (х '), где о равно 0 или 1, е > 1 и х'ф1'. Убедимся в эквивалентности функций, входящих в один и тот же класс эквивалентности. Имеем ~(Ох(1) х(2)...х(4)... ) = 0(х(1) э 0)(х(2) -е (х(1) э 0))... ... (х(1) — е (х(1 — 1) — е... — е х(1) э 0)... ))...
= = 0 х(1) (х(1) Ч х(2))... (х(1)Ч... Ч х(4 — 1) У х(1))...., 1(01'х(1) х(2)... х(1)... ) = О 1 ... 1 х(1)(х(1)Ч е Ч х(2))... (х(1) М... М х(1 — 1) Ч х(у))..., 1"(1 х(1) х(2)... х(1)... ) = 0 1 ... 1 х(1)(х(1)Ч х(2))... ... (х(1) Ч...Чх(1 — 1) Мх(1))...
(здесь 1 = 0 и при в > 1 слово 1 ... 1 пустое). е — 1 Отсюда заключаем, что каждая из остаточных функций Д(хб'"), 1е-. (хм) и Д. (хи), где е > 1, эквивалентна функции д(хи) = = у(1) у(2)... у(1)..., где у(4) = х(Ц У... Чх(1 — 1)ух(1), 1 > 1. Далее, Дее хз хз ... х, х(1) х(2)... х(1)... ) = = Охз (хз 'ехз) . ° ° (х1 хз " - " хе — 1)(х1 Ч хз М . ° ° Ч хе) Й 3е(х1 Ч хе... Мхов т(1))(т1 Мхе М... Ч хеЧ х(1)Ч х(2))...
110 Го. 1К Ограниченно-дегаерыинирооанные функции ... (хз Ч хз Ч... 'у х, Ч х(1) Ч х(2) Ч... Ч х(1))... = = Ох1(хз ~Гхз)...(х1 Ч хэ Ч ... Ч х,, з)11...1..., ибо х' ф 1' (а значит, хз Ч хз 'д... Ч х, = 1). Таким образом, ( я. (х(1) х(2)... ) = 1к. Из наших рассмотрений вытекает, что заданная функция ( является о.-д. функцией веса 3. в) Нарисовав пять полных ярусов и частично шестой ярус информативного дерева заданной функции (рис. 4.4), легко увидеть, на какие классы эквивалентности разбивается множество вершин этого дерева.
Вершина 0 образует один класс эквивалентности, все вершины, принадлежащие дереву, растущему из вершины 1, образуют второй Ро Рис. 4А класс эквивалентности; вершина 2 вместе со всеми вершинами четного ранга дерева Ро, растущего из нее (сама вершина 2 имеет в дереве Ро ранг 0), образует третий класс эквивалентности; наконец,. все вершины нечетного ранга дерева Ро образуют четвертый класс эквивалентности. Следовательно, рассматриваемая нами сейчас функция есть о.-д. функция веса 4. Все ее остаточные функции из упомянутого выше второго класса эквивалентны функции д(х ) = 1~. Остаточные функции, соответствующие вершинам четного ранга дерева Ро, эквивалентны функции уо(х ) = у(1) у(2)...
у(1)..., где (О, если 1 нечетное, у%= 11, если 1 четное. Наконец, остаточные функции, соответствующие вершинам нечетного ранга дерева Ро, эквивалентны функции ф(х' ) = у(1) у(2)... у(1)..., где (1, если 1 нечетное, у(1) = 10, если 1 четное. у д Отобралеенил ноеледоеительноетей 3. Выявление свойства детерминированности функции. Эквивалентность детерминированных функций. Остаточные функции. 1.1.
Пусть Дх(1) х(2)... х(1)...) = у(1) у(2)... у(1)... — функ- 1,1 ция из множества Рз'... Выяснить, является ли она детерминирован- ной,когда: 1) у(1) = х(1) и у(1) = х(1) Ю х(2) ф... Ю х(1) при 1 > 2; 2) у(1) = х(1) ~/х(2) ~д...'д х(1) М х(1+ Ц при 1 > 1; 3) у(1) = х(1) х(2) ... х(1)- х(1+ 2) — е х(1) при 1 > 1; 4) 9(1) = х([1о8,1]+1) при 1> 1; 5) у(Х) = х(з/[3,1(21)]) при 1 > 1; 6) у(1) = у(2) = 1 и у(й) = х(2' ~ — 1) при 1 > 3; 7) у(1) = х([31/4] + [~Д]) при Х > 1; 8) у(1) = 1 и у(1) = х(2+х(1)) при 1 > 2; 9) р(1) = у(2) = 0 и у(Х) = х(2-1- х(1)) при 1 > 3; 10) у(1) = 1 и у(Ю) = х(2+ у(à — 1)) при 1 > 2; 1, если существует такое целое 1 > О, что 1 = 2; ! 11) 9(1) = 0 в ином случае; ][1, если г < 100,.
(О, если 1 > 100; (х(201 — 1 — 90), если 7 < 1 < 13, 13) д(1) = 1 (О в ином случае; ( х(191 — 1~ — 80), если 7 < 1 < 12, 14) у(1) = с [1 в ином случае. 1.2. Выяснить, является ли детерминированной функция 1 из Рз '„,, д1 заданная следующим описанием: О, если хн = 0", 1 в ином случае; 1, если:е = 0", х(1)х(2)...
х(1)... в ином случае (здесь х(1)х(2)... х(1)... выходная последовательность, соот- ветствующая входной последовательности х'"' = х(1)х(2)... х(1)... ); 3) у(хн) = х(1)х(2)х(3)х(4)... х(2е — Цх(2е)... в ином случае (здссь х(1)х(2)х(3)х(4)... х(2е — 1)х(2е)... выходная последо- вательность, соответствующая входной последовательности х"' = = х(1)х(2)... х(1)... ); 112 Гл. 1К Огранинессно-денсерниниуованные функции 4) 7"(х ) = р(1) р(2)...суси..., где ( х(р), если 1 простое число, ср(1) = ' (0 в ином случае; 6)Пх )= х", если последовательность хх такова, что х(с) > ~сс2 для всех 1 = 1, 2, ..., с=1 0" в ином случае; 10) Дх ) = р(1) р(2)...р(1)..., где с 1, если ~ х(с) > —, ср(1) = ' 2' с=с 0 в ином случае; 11) Дхг ) = р(1) р(2)...срс(1)..., где р(1) = 1, если ~х(с+1) > —, 2' с=о 0 в ином случае; 12) Дх"'') = р(1) р(2)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
