Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 24
Текст из файла (страница 24)
х[в), составленная из букв алфавита А (здесь в > Ц. Кратко эта последовательность обозначается так: х'. Множество всех слов длины в в алфавите А (в > 1) обозначается через А'. Часто рассматривают и слово длины 0 [пустое слово), его обозначают символом Л. Через А* обозначается множество 1Л) 0 ] ) А'. Симз>1 вол вида [а1 ... а„]', где в > 2, п > 1 и аы .,., а, буквы из алфавита А, используется для краткой записи «периодического» слова оа ...он оп ... ан ...
аз ... о, (длины и в). Если и = 1, то вместо [аз]в применяют также символ а'. Бесконечные последовательности т' = х[1) х(2)... х[1)..., составленные из букв алфавита А, называются бесконечными словами в алфавигае А. Множество всех бесконечных слов в алфавите А обозначается через Ае. Слово ю, получающееся приписыванием слова юз справа к конечному слову им называется соединением слов юз и юз и обозначается через юзюз. Слово юз называют при этом префиксом [или началом), а слово соз - суффиксом (илн окончанием).
Слово х" = х(1) х(2)... из А ' называется кваэипсриодическим, если существуют такие целые числа по и Т, что по ) 1, Т ) 1 и х[п + Т) = х[п) при и > по. Префикс х(1) х[2)... х(по — 1) слова х ' в этом случае называют ирвдпериодом, число пв — 1 длиной пред- периода, слово х[по) х[по + Ц... х[по + Т вЂ” 1) —.- периодом слова х' ', а число Т вЂ” длиной периода Такое кв зипериодическос слово удобно записывать в виде х[1) х(2) ... х[ио — 1) [х(по) х[по + 1)... х[по + Т вЂ” 1)] Символом а" обозначается слово хе Е А~, в котором х[1) = а при любом 1 = 1, 2, ... (а ч А).
у 1. Отобраэеения последовап1ельноетей 103 Пусть А и В конечные непустые алфавиты. Множество отображений вида у: А ' э Во обозначается через Рл,в . Алфавиты А и В называют соответственно входным и выходным алфлвптамн отображения из Рл в, слова (последовательности) из множества А называют входными, а из множества В выходными. Отображение у из Рл н „, называется детерминированным оператором или с)етерминированной функцией (сокращенно: д. оператором или д. функцией), если оно удовлетворяет следующему условию; для всякого в > 1 и любого входного слова х (из А ) в-й символ выходного слова у = у(х ) является однозначной функцией первых е символов слова х''.
Множество всех д. функций из Рл в, обозначается через Рл,в,п. В тех случаях, когда А=Еьх ... хЕя (п>Ц, В=Е~х ... хЕ~ (гп>1), и раз п1 рпз где Еь=(0,1,,к — 1) (1е>2) и Е~=(0,1,,1 — 1) (1>2), множества Рл в и Рл в, будут обозначаться через Р,","„и Р„"', соответственно. Если отображение уэ = у(х'и) принадлежит множеству Р"',™„(или Р","и), то при т 2 вместо ул можно применять запись (у,..., у„'), а при и > 2 вместо Дхм) употреблять запись у(х"'', ..., х„); здесь у "г (~ = 1,..., т) переменная, пробегающая множество Е,", и х,"' (1 = 1, ..., п,) переменная, пробегающая поп 12,пп множество Еь.
При и = т = 1 верхние индексы у Р„,' и Р„', „ будем иногда опускать, т.е, будем писать Ря р, и Рву . Полагаем Рьа, = () Рь'~™'. Если 1 = й, то вместо двух индексов внизу будем п>з ш>1 писать один (например, Рь „). Функции уз и уз из множества Рл в „называются различимыми, если существует такое слово х~', (е > 1), что ~л(хо) т'- Ь(хе).
Если же уз (х') = 5(х") для любых слов х' (е = 1, 2, ... ), т, е. если равенство уз(х ) = )з(х' ) выполняется при всяком входном слове х, то функции )~ и уз называются эквивалентными (или неразличимыми) д. функциями. Пусть э' и д . функции из Рл и . Если существует такое слово хо с А*, что )'(хох' ) = У(хо)д(х"'') для любого слова х с А (здесь через Д(х') обозначен префикс длины в выходного слова Д(х'х )), то функция д называется остаточной функцией (или остаточным оператором) функции у, порожденной (порожденным) словом хо, и обозначается через )-..
Множество Я(у, х') всех остаточных функций функции у, эквивалентных функции ~в., образует класс эквива,лентностп, называемый состоянием функции Э, содержащим остаточную функцию );;. Состояние, содержащее функцию ), называется начальным. Функция у называется ограниченно-детерминированной (сокращенно о.-д. функцией или о.-д. операгеюром), если она имеет 104 Гл, Ре'. Ограниченно-детерминированные функции консчнос число попарно различных состояний.
Число различных состояний о.-д. функции называется вс весом. Если множество попарно различных состояний функции 1 бесконечное, то считают, что вес ее равен со. Множество всех о.-д. функций, принадлежащих множеству Рл и „(соотвстстввнно множествам Р, ',, Р, ', Ря ~ „и Ря л), обозначается через Рд и, (соотвстственно через Р„"',"",, Р„"'„"', Рь ~ и Рь„). При описании д. функций бывает удобно пользоваться теоретикографовым языком (а имснно бесконечными информативными деревьями). Пусть А алфавит, состоящий из 1 букв (1 > 1). Через Рл обозначим бесконочное ориентированное корневое дерево *), удовлетворяющее следующим условиям: а) из каждой вершины дерева, включая и корень, выходят ровно 1 дуг (т.
с. ориентированных ребер); б) в каждую вершину дерева, отличную от корня, входит только одна дуга, а в корень дерева нс входит ни одной; в) каждой дуге дерева Рл приписана некоторая буква алфавита А, причем разным дугам, выходящим из одной и той же вершины дерева (в частности, из корня), приписаны разные буквы. Корень дерева Рл считается вершиной нулевого ранга; если вершина дерева Рл является концом дуги, выходящей из вершины ь'-го ранга (1 > 0), то она называется вершиной (1+ 1)-гег ранга. Лугой (ребром) у-го яруса 0 > Ц называется всякая дуга, выходящая из вершины 0 — 1)-го ранга. Каждой бесконечной оривнтированной цепи в дереве Рл соответствует вполне определенное слово из множества А . Па рис. 4.1 изображен фрог- 0 Рис.
4.1 Рис. 4.2 лент дерева Рл (где А = (О, 1)), состоящий из трах первых ярусов этого дерева (здесь и в дальнейшем мы предполагаем, что символу 0 соответствует левое ребро (дуга), выходящее из вергпины, а символу 1 правое); жирными ребрами выделена цепь, соответствующая слову 101. Нагруженное дерево Рл в получается из дерева Рл приписыванием каждой дуге некоторой буквы из алфавита В. Всякой бесконечной ") Определение корневого дерева см.
в гл. У1. у д Осаобрансенин последовательностей 105 ориентированной цепи в дереве Рл и отвечает слово из множества В', составленное из букв, приписанных дугам этой цепи. Поэтому можно считать, что нагруженное дерево Вл н задает, (реализует) вполне определенное отображение у: А'' -э В", являющееся д. функцией из множества Рл д . На рис. 4.2 изображен фрагмент нагруженного дерева Вл н, где А = (О, 1) и В = (О, 1, 2); д. функция, соответствующая этому дереву, «перерабатывает», например, слово 1010 в слово 2012.
Пусть Вл н — нагруженное дерево, реализующее д, функцию 1. Остаточной функции 5„-,. (в > 0) отвечает поддерево Вл д(хо), растущее из такой вершины о(х') в-го ранга, в которой оканчивается цепь, выходящая из корня дерева и содержащая ровно в ребер; 1-е по порядку ребро этой цепи принадлежит 1-му ярусу дерева и помечено символом хо(1) ч А. Если остаточные функции Д1 и (я эквивалентны, то соответствующие им вершины о(х') и о(х"), а также растущие из этих вершин поддеревья называются эквивалентнеллси. Вес дерева, реализующего д, функцию, равен весу этой функции, а следовательно, равен жаксилсальноду числу попарно неэквивалентных вершин (или поддеревьев) данного дерева. 2.
Типовые примеры. Пример 1. Выяснить, является ли д. функцией отображение у" = 1(х"') Е Р,', где х" = х(1)х(2)... х(1) ..., у" = у(1) у(2)... ...у(с)... и у(е) = х(1) — э х(1) при 1 > 1. Решение. Из описания функции следует, что значение «выхода» у(с) в момент времени 1 однозначно определяется значениями «входа» в моменты времени 1 и 1, т.е. в-й символ выходного слова у' при всяком в > 1 является однозначной функцией первых в символов входного слова х".
Значит, рассматриваемая функция детерминированная. Пример 2. Является ли функция у детерминированной, если у = з(х ) к Рз'„,, где х = х(1)х(2)... х(1) ..., у ' = у(1) у(2)... ...у(1)... и ~(х(1 — 1)., если Е четное число, у(1) = з (х(1) у(1+ 1), если 1 нечетное число? Решение. Если ориентироваться на форму задания функции, то естественно предположить, что она не является детерминированной, так как, например, «выход» в момент времени 1 = 1 зависит от «выхода» в момент 1 = 2.
Однако указанная зависимость может оказаться «фиктивной», возникшей только вследствие «плохого» (неудачного) описания функции. Поэтому необходимо проанализировать «природу» рассматриваемой функции. Пусть 1 = 2в+ 1, где в > О. Имеем у(2в + 1) = х(2в + 1) у(2в + 2) = х(2в + 1) . х(2в + 1) = = О. Следовательно, при всяком нечетном 1 выход у(1) равен О, т.е. 106 Гт 1К Ограниченно-детерминированные. функции является однозначной функцией первых 1 символов входного сло- ва х"'.
Очевидно также, что аналогичная однозначность имеет место и для четных значений й Таким образом, рассматриваемая функция детерминированная. Пример 3. Выяснить, является ли д. функцией отображение у = 1(хы) Е Р '„,, где х'' = х(Цх(2)... х(1)..., у ' = у(Ц у(2)...
...,у(1) ... и О, если существует такое в <1, у(1) = что Зх(в) < х(в + Ц + х(в + 2), 1 в ином случае. Решение. При х(в) = 0 неравенство Зх(в) < х(в+ Ц + х(в+ 2) выполняется независимо от значений х(в+ Ц и х(в -ь 2), а при х(в) = = 1 оно не выполняется ни при каких значениях х(в+ Ц и т(в+ 2). Следовательно, О, если х(в) = 0 при некотором в < 1ч у(1) = 1 в ином случае, т. е. отображение 1" является д. функцией. Пример 4.
Пусть уч' = те(х~) Е Рг'„где хы = х(Цх(2)... ... х(1)..., у = у(Ц у(2)... у(1)... и у(1) есть (1+ 2)-я цифра после запятой в двоичном разложении числа х(1)1'6. Выяснить, явля- ется ли д. функцией отображение 1'(хн). Решение. Из описания функции видно, что выход у(1) в мо- мент времени 1 определяется однозначно значением входа х(е); надо просто найти (1 + 2)-ю цифру после запятой в двоичном разложе- нии числа х(1)/6.
Значит, рассматриваемая функция является де- терминированной. Запишем выход у(1) в «явной форме». Нетрудно 1 1 1 1 1 установить, что — = — + — + — + ... + + ... Следовательно, б 8 32 128 2 4' двоичное разложение числа 11'6 имеет вид 0,0010101... = 0,0 (ОЦ,. а |юзтому 1., если х(1) = 1 и 1 = 2в + 1, где в > 1, у(1) = 0 в иных случаях. Пример 5. Показать., что оба приводимых ниже отображения у~ = 1(ххи) (из Р ',) не являвотся д. функциями (здесь, как обычно, х" = х(Ц х(2)... х(1)... и у ' = у(Ц у(2)... у(1)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
