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