Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 27
Текст из файла (страница 27)
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' из Рд л называется автономной (или константой, или функцией без выхода), если она принимает постоянное значение (на множестве А"'), т. е. если на любом входном слове х Е А функция ( равна одному и тому же (выходному) слову из В Выяснить, является ли автономной функция ( Е Рз ,и если она автономна,то найти ее вес: 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) множество всех функций из Р '„, зависящих от переменной йд и таких, что в соответствующих им деревьях в любой цепи, вы- ходягдсй из корня, две единицы не могут быть приписаны соседним дугам; 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) и концы этих дуг, т. в. вершины ш1 и шз, имеют одинаковые номера.
Опсрация склеивания (эквивалентных) сошлояний состоит в следующем: вершины с одинаковыми номерами «стягиваются» в одну вершину, а появляющиеся при этом параллельныс*) одинаково помеченные дуги заменяются одной дугой (с твм жо направлением), несущей ту же пометку. Вершина и диаграммы Мура называется достижимой иэ (начальной) вершины и, если существует ориентированная цепь, выходящая из вершины и и заходящая в вершину и. Начальная вершина считается по определению достижимой.
*) Дуги в ориентированном графе называются параллельными, если они соединяют одни и те же вершины и нх направления совпадают. »" г, »»иаграммьь тпаблицы, канонические уравнения, схемы 127 Операция исключения (удаления) недостижимых вершин состоит в удалении из диаграммы всех вершин, не являющихся достижимыми. Диаграмма, в которой нет ни одной пары эквивалентных вершин и все вершины достижимые, называется приведенной диаграммой.
Недостижимые вершины можно найти, просматривая в диаграмме все ориентированные цепи, выходящие из начальной вершины. Эквивалентность вершин можно устанавливать, используя непосредственно определение эквивалентных вершин или строя по диаграмме информативное дерево, соответствующее ей (и той о.-д.
функпии, которую эта диаграмма описывает). С помощью информативных деревьев легко устанавливается справедливость следующих утверждений. а) Операция исклкьчения недостижимых вершин в диаграмме Мура о.-д. функции приводит к диаграмме, роализующей ту же функцию. б) Операция склеивания эквивалентных вершин, примененная к диаграмме Мура о.-д. функции, приводит к диаграмме, реализующей ту же функцию.
в) Число вершин в приведенной диаграмме Мура о.-д. функции равно весу этой функции. С диаграммой Г» функции» можно связать две функции: а) Р: А х Π— э В (функция выходов); б) О: А х Я вЂ” э 1„1 (функция переходов). Функции Р и С по орграфу Г» определяются так: по паре (а, ») находим вершину» и такую дугу, исходящую из», которой приписан входной символ а (пусть эта дуга есть (», 1)): значением функции Г на паре (а, ») является выходной символ, приписанный дуге (», 1) и стоящий в скобках за символом а; значение функции 1» на паре (а, ») совпадает с 1, т. е. равно «номеру» того состояния, которое «является концом» дуги (», 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
