Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 27
Текст из файла (страница 27)
4) В задаче 3) изменим только одно условие: если 1 < 1 < 1, то у(1) = 1. Обозначим новую функцию через 1"ы Доказатгн что: а) у функции г1 в точности два бесконечных класса эквивалентности остаточных функций, и элементы одного из них являются функциями веса 2, а другого порожденными функциями; б) остальные классы эквивалентности остаточных функций функции 1'1 конечные, и при 1 > 2 среди них ровно 1+ 1 одноэлементных классов; в) вес фУнкции уз Равен 21+ 1. 5) Функция д' из Рз определяется следуквщим образом: О ... 0(1), если х = 0... 0 х(1+ 1) х(1+ 2) ..
1(хч' ) = 0" в ином случае, произвольное фиксированное целое число, нс меньшее 1. Доказать, что: а) функция 1 имеет ровно два бесконечных класса эквивалентности остаточных функций, и элементы каждого из них . - порожденные функции; б) остальные классы эквивалентности у функции г" одноэлементные: в) для каждого г, удовлетворяющего неравенствам 3 < г < 1+ 2, у функции Г существует единственная остаточная функция веса г. 1.14.
Выяснить, сколько у функции г" Е Рз конечных и сколько бесконечных классов эквивалентности остаточных функций, выписать явно (в какой-либо форме) все остаточные функции (по одной из каждого класса эквивалентности) и найти их веса: ('у(1) = О, ) ~' (у(1) = х(1) Юх(1) Ю1, 1 > 2; ( у(1) = 1, 2) 1: у(1) = х(1).х(1), г > 1; 3) 1: '( (1) (1) ~ (1 1) 1 > 2 123 у Д Отобрадсения последовательностей 4 ( у(Ц = х,(Ц, ) ~' [ у(1) = у(1 — Ц, 1 ) 2; *) д ' [ у(1) = х(1) — «у(1 — Ц, 1 ) 2; 6) ((хч ) = [010) ; [ОЦ", если х = 0 [ОЦ'1х(21+2)х(21+3)..., если х ' = = Оз'1х(21+ 2) х(21 + 3)... и 1 > 1, [ОЦ х(2/+Цх(21+2)..., если х =0«Я '1х(21+ Цх(21+2)...
и 1 >1., 7) ((х ) = х в ином случае; 8) «е(х") = [Ох(Ц); 9) ((хм) = [х(Ц х(2) Ц"; ( у(Ц = у(2) = О, ) (' [у(1) = х(1 — 2) 6«х(1)., 1> 3. (у(Ц =О, ) «з,д У ~у(й) у(1 Ц 1) 2. (у(Ц =1 )У ад,( [у(1) х(2) х(1 Ц «х(е Ц 1)2. 3) ( Е Рз"„' и (: у(1) = х(Ц ... х(1) — «х(Ц х(1), 1) 1; у(с) = х(Ц вЂ” «(х(с) — «х(Ц), если 1 = Зв — 2, в > 1, и (; у(1) = у(1 — Ц вЂ” «(1 — Ц х(й) если 1 = Зв — 1, .з > 1, у(1) = у(1 — 2) 6«у(1 — Ц, если 1 = Зв, в > 1; 4) ( е Ра'~ (у(Ц = О: ~' '[ у(1) = х(2) -+ (х(Ц вЂ” «х(1)), 1 ) 2; у(1) = 1, если 1 = 2' (ъ' = О, Ц 2,... ), 6) ( Е Р,'д и (; у(1) =у(Ц |Зу(2) ЕВ...
Фу(Х вЂ” Ц в ином случае: 1.15. Функция 7' из Рд л называется автономной (или константой, или функцией без выхода), если она принимает постоянное значение (на множестве А"'), т. е. если на любом входном слове х Е А функция 1 равна одному и тому же (выходному) слову из В Выяснить, является ли автономной функция ( Е Рз ,и если она автономна,то найти ее вес: 124 Га. 1'е'. Ограниченно-деигерминированкые функции у (1) = О, если г!+1 <1< (и+1)1, 7) ~ Е Рг '„и 4'; г=0,2,4, ..,,2ш,.
УЖ = У~И вЂ” 1+ 1) в ином случае (здесь | — произвольное фиксированное число, не меньшов 2); у,(1) =1, уг(1) = О, уг(г) = х(1) е (уг(1 — 1) в у (1 — 1)), 1 > 2, уг(1) = уг(1 1) ~ уг(1 1)х(1); 1 ~ )2! 8)У~Рг';,' и У: У,~1) =х(1) х(1) -вх~1)., 1>1, 9) 1" Е Рг' и г': Уг(1) = О, угф = уг(1 — 1) — г уг(1 — 1), 1 > 2; уг(1) = уг(1) = 1, 10) ~ Е Рг' и ~: уг(1) = хЯ -+ уг(С вЂ” 1)уг(Х вЂ” 1), 1) 2, уг(1) = х(1) х(2)... х(1) -+ х(2) уг(1 — 1), 1 > 2; у,(1) =1, уз~1) = О, 1 1 ) ~ Е Р и ~ у ( ~ ) у ( ~ 1 ) е > уг(1) = уг(1 — 1) г уг(1 — 1) х(1 — 1), 1 > 2. 1.16.
1) Доказатги что если г — о.-д. функция из Ря и д то для всякого квазипериодического слова х (из А ') слово 1(х ) также квазипериодическое. 2) Утверждение, обратное к сформулированному в 1), неверно. Покажите это, используя следующую функцию 1'1хи) = гд(Ц гд(2)... ...
у(1)... из множества Р ': У(1) = ' '(1). '(2).....х '(1), где 1>1, х(г), если еее = О, х(з), если ег; = 1, х и пгцг...щ префикс длины 1 слова 0101101110...,. в котором нули стоят только на местах с номерами (г), ф = 2, 3, 4, 5,... (Другими словами, функция ~(х~) такова, что в реализующем ее дереве символ 1 приписан только дугам, которые принадлежат ориентированной цепи, исходящей из корня и соответствующей входному слову 010110111011110...; остальным дугам дерева приписан 0.) 1.17.
1) Пусть Вя и — — нагруженное дерево веса г > 1. Доказать, что для каждой его вершины найдется эквивалентная ей вершина ранга не выше г — 1. у 1. Оеаобранеенин яоследооагаельаостеа 125 2) Пусть г > 2. Показать, что в задаче 1) заменить г — 1 на г — 2, вообще говоря, нельзя. 1.18. Пусть все вершины нагруженного дерева Вл и разбиты обычным образом на классы эквивалентности. Показать, что, каков бы ни был класс эквивалентности дерева Вл и, в нем существует такая вершина е, что в ориентированной пепи, исходящей из корня дерева и оканчивающейся в вершине г, все вершины попарно не эквивалентны. 1.19. Найти мощности следующих множеств: 1) множество всех отображений вида 1": 10, 1) ' -+ 10, 1)'е, завися- щих от (фиксированной) переменной тз, 2) множество всех одноместных д. функций вида 1: 10, 1)"' — ~ — е 10, 1)"'', зависящих от (фиксированной) переменной йг, 3) множество всех одноместных о.-д.
функций вида 7': 10, 1) — е -о 10, 1)~, зависящих от переменной тт~; 4) множество всех автономных функций (см. задачу 1Л 5), принадц1 и. лежащих множеству Р ' и зависящих от переменной я 5) множество всех порожденных д. функций (см. задачу 1.11), принадлежащих множеству Рэ ', где и > 1, и зависящих от переменод ных я,тэ, ...
и„; 6) множество всех функций из Р '„., зависящих от переменной т1~ и удовлетворяющих следующему условию: в соответствующих им деревьях, начиная с 1-го яруса, стоят только нули (здесь 1 > 1 и фиксировано); ц1 М 7) множество всех функций из Р ', зависящих от переменной и' и таких, что в соответствующих им деревьях единицы могут стоять только на дугах, принадлежащих цепи, отвечающей входному сло- ву о 8) множество всех функций из Рэ'„ зависящих от переменной й, и удовлетворяющих следующему условию: в соответствующих им деревьях число единиц конечное (хотя может быть сколь угодно боль- шим); 9) множество всех функций из Р '„, зависящих от переменной т1 и таких, что в соответствующих им деревьях в любой цепи, вы- ходягдсй из корня, две единицы не могут быть приписаны соседним дугам; 10) множество всех функций из Р ', зависящих от переменной йгн и таких, что в каждом ярусе соответствующих им деревьев; а) находится только один нуль (остальные выходные символы единицы); б) число нулей равно 2; в) число нулей равно числу единиц; г) число нулей меньше числа единиц.
126 Гл. Гг'. Огроничгнно-дешеуминирооанныг функции 2 2. Диаграммы, таблицы, канонические уравнения, схемы 1. Диаграммы Мура, канонические таблицы и канонические уравнения. Пусть 1,) = Яо, Цы ..., Я„1) -- множество всех состояний функции у из Рл в, . Сопоставим функции 1 ориентированный граф Гу, задаваемый следующим образом: 1) множсством вершин орграфа Гу является множество Еы = = 10, 1, ..., и — 1), причем считается, .что вершина ф соответствует состоянию О 2) если ~~6 и )® остаточные функции, реализуемые соответственно состояниями я, и ф, и ~О~ являвтся остаточной функцией функции ~б~, порождаемой словом х~ = а, причем уб~(ахы) = = 6~®(хы), то в орграфе Гу имеется дуга (1, ф), и ей приписывается выражение а(6); 3) дуга (1, Я существует в Гу только при выполнении условий и.
2). Вершина из Гу, соответствующая начальному состоянию функции у, обычно отмечается звсздочкой. Пусть из вершины 1 в вершину ф идут ш дуг, которым приписаны выражения а1(61), аз(Ьз),..., а„, (6~) (здесь обязательно ав ф ао при р ~ а, но некоторые или все символы 6, могут совпадать друг с другом); тогда будем соединять г с ф только одной дугой (1, ф) и будем приписывать ей все выражения ар(Ьр) (р = 1, 2,..., т).
Орграф Гу называется диаграммой Мура функции 1. Две верьпины и1 и из диаграммы Мура называются эквивалентными, если всем вершинам диаграммы можно так сопоставить натуральные числа (номера), что будут выполняться следующие условия: а) номера вершин оз и из совпадают; б) если из и иг — две произвольные вершины с одинаковыми номерами, то, каков бы ни был входной символ а, дуги (иы ш1) и (из, шз), соответствующие ему, имеют одинаковую пометку а(6) и концы этих дуг, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
