markov_teorija_algorifmov (522344), страница 33
Текст из файла (страница 33)
е. нельзя ли построить такой нормальный алгорифм Й в алфавите А, что для любого слова Р в А будет й (Р) Ц[Р-. Ответ на этот вопрос оказывается, вообще говоря, отрицательным, как показывает следующее утверждение; 3.1, Если алфавит А содержит более одной буквы, то не существует никакого нормального алгорифма й в А, который для любого слова Р в А удовлетворял бы условию й(Р) ж[Р . В самом деле, пусть й — такой чормальный алгорифм. Покажем, что 3.2. Если слово Р таково, что Р з [Р, то Й: Р ( — [Р Действительно, пусть РЯР .
Тогда Й: Р)=[Р ) или й: Р)= [Р . В первомслучае, содной стороны,й([Р ) ~[Р а с другой стороны, й ([Р ) 7А[[Р . Но [[Р Б Р, и, таким *) См. В ЗНЗ. иц з зз зз] АЛГОРИФМЫ ПОБУКВЕННОГО КОДИРОВАНИЯ образом, Р Х [Р, что противоречит условию. Следовательно, й: Р )= [Р, и потому существует слово (г такое, что й: Р ~ 1г и й: Я )- [Р [3 25,7]. Возьмем такое Я. й: Я=.[Р и, значит, Й(®32[Р . С другой стороны, Й вЂ” обращающий алгорифм, и поэтому Й(Я)я.[Я . Таким образом, [Р Х[~, и, значит, Р л.
Я, откуда Й' Р )- [Р , что и требовалось доказать. Продолжим теперь доказательство утверждения 3.1. Так как алфавит А содержит более одной буквы, то имеются слова Р в А такие, что Рд' [Р . Отсюда следует, что в схеме Й имеются заключительные формулы подстановок. Возьмем первую из них. Пусть это будет формула у- у. Выберем в алфавите А две буквы Б и Ч такие, что У не начинаегся $ и что $ 1Г' з1.
Рассмотрим слово МУРР Легко видеть, что 1"ЕУЧ ми[У з„и потому [$Ул1 ~г'$Уз1, так что Й: $Ул1 1- з1[У э, причем активной на слове $Уз1 является именно формула У- )Г, так как ее левая часть входит в ~Уть а все предшествующие формулы подстановок простые. Предположим, что У м.Л. Тогда $Уз1.В'. $з1 и й: эз) )- )ГЕП. Отсюда з1$Х)Г~П, и, значит, ~Хз1, что противоречит выбору Б и з1. Следовательно, у -,РЛ. Но если У ~Л, то аль У зе з1 †перв вхождение слова У в слово $Уз1, и потому й: $Ул) 1- ° $рз1. Следовательно, з)[У 5ХУ/Ч, и, значит, ~Х ть что снова противоречит выбору $ и т1. Следовательно, неверно, что У ~г Л.
Таким образом, мы, с одной стороны, доказали, что У л1' Л, а с другой стороны, опровергли предположение о том, что У г Л. Значит, неверно, что для любого Р в А Й(Р) я.[Р, что и доказывает 3.1. Заметим, что если алфавит А однобуквенный или пустой, то тождественный нормальный алгорифм в А, определяемый схемой является обращающим. й 33. Алгорифмы побуквенного кодирования и двойного проектирования 1, Поставим в соответствие каждой букве $ алфавита А определенное слово Кг в этом алфавите.
Заменяя в произвольном слове Р в А каждую букву э поставленным ей 172 НОРМАЛЬНЫЕ АЛГОРИТМЫ !ГЛ. ГН в соответствие словом Кь мы получим слово в алфавите А — результахп замены букв $ словами Кд в слове Р. Результат замены букв Б словами Кз в слове Р мы будем обозначать символом Ф (Р). Более точное — „рабочее" — опре- деление этой операции мы дадим посредством равенств Ф(Л) Л, Ф(Р$) — Ф(Р) Кз, где Р означает произвольное слово в А, а $ — любую букву алфавита.
Легко видеть (это доказывается методом праной индук- ции), что для любых слов Р и Я в алфавите А Ф(Р0) -Ф(Р) Ф(()). Кроме того, Ф($)'хК. Нетрудно построить нормальный алгорифм над алфавитом А, выполняющий замену букв $ словами Кы т. е. перерабатывающий всякое слово Р в А в слово Ф (Р). В самом деле, пусть а не принадлежит А. Зададим нормальный алгорифм мд в Аа сокращенно записанной схемой а$ — Кда а — .
где $ пробегает А. Покажем, что для любого Р в А Йд (Р) Х Ф (Р). Из рассмотрения схемы (1) имеем 1.1. Йд. 'Р ) — аР. 1.2. Асд. Ф(Р) а$Я )- Ф(Р5) аЯ. 1.3. Йд. Ра )- ° Р. Далее, имеем 1.4. Йд'. аРЯ ~= Ф (Р) аЦ. Доказывается правой индукцией по Р с использова- нием 1.2. 1.б. Агд: аР)=Ф(Р) а. Частный случай 1.4 при ЯХЛ.
Из 1.1, 1.5 и 1.3 следует (2). Действительно, 'пд Р ) а~ [1 ° 11 ) Ф(Р) а [1.51 )- Ф(Р) [1.31, АЛГОРНФМЫ ПОБУКВЕННОГО КОДНРОВАННЯ дам 173 т. е мд. Р~= Ф(Р), дед (Р) ХФ(Р), откуда Тот же результат дает более простой нормальный алгорифм в А, определяемый сокращенно записанной схемой й-! в которой 5 пробегает алфавит А' ). 2. Важным частным случаем замены букв словами является выбрасывание некоторых букв.
Это — тот частный случай, когда К1ХЛ для некоторых букв $ и КБХ$ для остальных $. В связи с этой операцией в дальнейшем будет применяться следующая терминология. Пусть А — расширение алфавита Б. Результат выбрасывания букв алфавита А" Б из слова Р в А мы называем проекцией слово Р на алфавит Б и обозначаем через [РБ (см. % 19.3). Построение проекций слов в А на Б мы будем называть операцией проектирования из А на Б. ,Соответствующим частным случаем алгорифма йд является нормальный алгорифм в Аа с сокращенно записанной схемой аз $а ац- а где $ пробегает алфавит Б, а ц — алфавит А'~Б. Однако более простой нормальный алгорифм в А с сокращенно записанной схемой Д что и требовалось доказать.
Рассмотрим случай, когда ( есть буква алфавита А и любой букве $ этого алфавита в качестве Ке сопоставляется слово ) . Очевидно, что в этом случае для любого слова Р в А ~А (Р) ['~ НОРМАЛЬНЫЕ ЛЛГОРИФМЫ 1гл. ! н где $ пробегает А' Б, очевидно, достигает той же цели— он перерабатывает всякое слово в алфавите А в проекцию этого слова на алфавит Б и, следовательно, вполне экви- валентен кл относительно А. 3. П кого сло . Пусть А и Б — алфавиты без общих букв. Дл ля всяова Р в объединении этих алфавитов возможно построить как проекцию [РА на алфавит А, так и проек- цию [Рв на алфавит Б. Покажем, что нормальный алго- рифм Вх в в алфавите АБ с сокращенно записанной схемой (т1$ - $Ч, где й пробегает А, а т1 пробегает Б, переоабатывает вся- кое слово Р в алфавите АБ в слово [Рх[Рй. Для этого условимся прежде всего называть высотой слова Р в алфавите АБ число вхождений в Р слов вида т)Д$, где $ — буква А, т1 — буква Б, а 1;1 — любое слово в АБ.
Высоту слова Р будем обозначать символом [Р'. Докажем некоторые леммы. 3.1. Если Р,— слово в АБ, ~ — буква Б, то (1) [Р -[~") В самом деле, соотнесем всякому вхождению (2) 5 !К т1Я ть Т слова вида т11;1Я ($ — буква А, т1 — буква Б) в Р вхождение (3) 5 !к !ЯК !х Т~ зом того же слова в )с». Вхождение (3) будем называт б вхождения (2). Очевидно, что разные вхождения слов вида ЧЯ (э — буква А, Ч вЂ” буква Б) в )с имеют разные образы. Р ассмотрим, с другой стороны, какое-нибудь вхождение (4) Уж!1яжр слова вида т111ч (й — буква А, т1 — буква Б) в Тс!",.
Имеем (5) и )ВРАЛ~, Здесь $ф'.!., так как $ — буква А, !,— буква Б. Поэтому $'~'Л и )» оканчивается буквой ~, т. е. (6) ух йгь. см. 4 18.!О. е) Относительно применяемой ниже арнфметичесией символики З за! ЛЛГОРИФМЫ ПОВРКВЕННОГО КОДИРОВХНИЯ 175 Имеем УЧЖ~'я.(с [(6) (6)1 откуда следует, что (7) У !К т111 $ !К (т' есть вхождение т1Я в Я. В силу (6) вхождение (4) есть образ вхождения (7). Таким образом, всякое вхождение слова вида !Д$ ($ — буква А, ц — буква Б) в 7(~ есть образ некоторого вхождения того же слова в К. Следовательно, соотнеся каждому вхождению слова вида т)(Д (5 — буква А, т1 — буква Б) в )с его образ, мы тем самым установили взаимно однозначное соответствие между вхождениями таких слов в )с, с одной стороны, и их вхождениями в Я~ — с другой.
Поэтому имеет место равенство (1), что и требовалось доказать. 3.2. Если тс — слово в АБ, Г,— буква А, то (6) [)!1Г = [Р'+ [[Р"-з. В самом деле, определим образ вхождения слова вида тф$ ($ — буква А, 9 — буква Б) в )с, как в доказательстве предыдущей леммы. Вхождения слов этого вида в Я(,, являющиеся образами вхождений таких слов в )с, будем называть вхождениями 1-го рода. Они находятся во взаимно однозначном соответствии со вхождениями слов вида т1К (й — буква А, т1 — буква Б) в К, и число их поэтому равно ф'.
Поставим далее в соответствие каждому вхождению (9) 3 * 3 * Т какой-нибудь буквы т алфавита Б в слово Р вхождение (1()) Ежтт1ж слова 1(Т~ в тсь. Вхождение (10) также будем называть образом вхождения (9). Так как Ь вЂ” буква А, образ всякого вхождения буквы алфавита Б в Я есть вхождение слова вида тЩ (5 †бук А, т1 †бук Б) в й!~, Разные вхождения букв алфавита Б в К, очевидно, имеют разные образы, т. е.
соответствие между этими вхождениями и их образамн взаимно однозначно. Будем называть вхождениями 2-го рода образы вхождений букв алфавита Б в слово Р. Число вхождений 2-го рода равно числу вхождений букв алфавита Б в )ч', т. е. оно равно [[1~аз. Ни одно вхождение 1-го рода не может быть вхождением 2-го рода, так как вхождения 1-го рода имеют непустое правое крыло, а вхождения 2-го рода — пустое правое крыло.
!76 [гл. Ри НОРМАЛЬНЫБ АЛГОРИФМЫ Всякое вхождение слова вида т!Я ($ — буква А, т!— буква Б) в ЯЬ является вхождением 1-го или 2-го рода. Действительно, рассмотрим какое-нибудь вхождение (4) слова этого вида в ттЬ". Если )»~ЕЛ, то, рассуждая„как в доказательстве предыдущей леммы, убеждаемся, что (4) есть образ некоторого вхождения того же слова в 1с, т. е. вхождение 1-го рода. Если УХЛ, то (4) является, очевидно, ОбраЗОМ ВХОждЕНИя У»вт!»К!Е буКВЫ т! авфаВИта Б В 1С, т. Е.
вхождением 2-го рода. Таким образом, число вхождений слов вида т)Щ (Б— буква А, т! — буква Б) в Рть" равно сумме чисел вхождений 1-го рода и 2-го рода, т. е. сумме чисел [)т' и П)тва, что и выражается равенством (8). 3.3. Если К вЂ” слово в АБ, а Ь вЂ” буква этого алфавита, то [РР [)»в 1 (ПЕБд Х П~ла) В самом деле, ПЬАа есть 1, если ь — буква А, и О если ь — буква Б. В силу этого З.З следует из 3.1 и 3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
