Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 23

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 23)

е. для любых двух классов В, и В, из семейства (Вт) справедливо только одно из включений: Вт, С В, или В, й Вэ, . Глава 1Ъ" ОГРАНИЧЕННО-ДЕТЕРМИНИРОВАННЫЕ Фо'НКЦИИ 2 1. Отображения последонательностей 1. Основные понятия н факты, связанные с заданием детерминированных функций. Пусть А непустой конечный а фавипк Его элементы называются буквами (или символами). Словом длины в в алфавите А называется последовательность вида х(1) х(2)... х[в), составленная из букв алфавита А (здесь в > Ц. Кратко эта последовательность обозначается так: х'.

Множество всех слов длины в в алфавите А (в > 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 является однозначной функцией первых в символов входного слова х".

Характеристики

Список файлов книги