markov_teorija_algorifmov (522344), страница 29
Текст из файла (страница 29)
3. Схему 2(1) нормального алгорифма ВА а, первые три формулы подстановки которой имеют „общий вид" е$ $е, где $ — произвольная буква А, удобно записывать в следую- щем сокращенном виде: ( ея Ее (2) е— — е, дополнительно указывая, что $ пробегает алфавит А. При расшифровке этой записи мы придаем $ последовательно значения а, 5, с, соблюдая — для конкретности — порядок букв в А (что, впрочем, в данном случае не играет особой роли). Аналогичную сокращенную запись мы будем употреблять и в других случаях, делая по мере надобности необходимые пояснения. Просмотрев доказательства утверждений 2.1 — 2.7, читатель без труда убедится, что трехбуквенность алфавита А в них никак не используется. Алфавит А здесь можно считать произвольным. Мы так и поступим, и будем считать, что алгорифм ВА О окончательно определяется схемой (2), где А — произвольный алфавит.
Утверждения 2.1 — 2.7 мы будем считать доказанными именно для этого алгорифма. 4. Алгорифмы ЙА, а и ВА, о естественно называть присоединяющими алгорифмами; алгорифм ЙА, о — левым присоединяющим (слово 11) алгорифмом над алфавитом А, алгорифм ВА, о — правым присоединяющим (слово 1е) алгорифмом над алфавитом А. Частным случаем левого присоединяющего алгорифма над алфавитом А является тождественный нормальный алгорифм ЭА в алфавите А, определяемый как ЙА, А.
Для него имеем ВА(Р) 7.Р для любого слова Р в алфавите А [1.11. 5. Нормальный алгорифм ВА в алфавите А, определяемый схемой мы будем называть пустым нормальным алгорифмом в А. Фактически мы уже показали [$ 25.11.41, что ВА не применим ни к какому слову в алфавите А. 9 29. Сокращающие алгорифмы 1. Будем говорить о простой формуле подстановки, что она сокращающая, если длина ее правой части меньше длины ее левой части. Будем говорить о нормальном ал гор ифме, что он сокращаюи1ий, если все его простые формулы подстановок сокращающие. Следующая лемма очевидна: 1.1.
Если Й вЂ” сокращающий алгорифм и Й:Р) — (г, то [г'<[Р'. Имеем далее 1.2. Любой сокращающий алгорифм Й в алфавите А применим ко всякому слову Р в алфавите А, причем имеет место неравенство (1) (Й:Р) ( [Р»1. Будем доказывать эту теорему методом индукции по длине слова Р, фиксируя сокращающий алгорифм Й. Алгорифм Й применим ко всякому слову длины Л и для всякого такого слова Р имеет место неравенство (1).
В самом деле, если [Р» Р Л, то Ря.Л. Никакая простая формула подстановки вэтом случае не действует на Р, так как ее левая часть непуста. Если алгорифм Й действует на Р, то формулой, активной на Р в Й, является заключительная формула подстановки. Тогда имеется слово 1г такое, что Й: Р) — 1',1, и мы имеем (Й; Р) ~( [9 25.8], откуда следует, что алгорифм Й применим к Р. Если же Й не действует на Р, то (Й: Р) хЛ [9 25.8.81.
В обоих случаях алгорифм Й применим к Р и имеет место (1). Предположим теперь, что для натурального числа М доказано, что алгорифм Й применим ко всякому слову в А длины, не большей М, и что для всякого такого слова имеет место неравенство (1). Пусть Р— слово в А длины М). Имеет место одно из трех: 1) Й:Р~1; 2) имеется слово 1е такое, что Й: Р ) — ° (г; 3) имеется слово 1Е такое, что Й: Р 1- (). В первых двух случаях алгорифм Й применим к Р и (Й: Р)(~ [9 25.81.
В третьем случае [Д» < [Р» [1,21 и потому [1е (М. По индуктивному предположению отсюда следует, чтоалгорифмй применим к Я и что (Й: 1Е) ( ( [1Е» ). Следовательно, алгорифм Я применим к Р и (Я: Р) лг Х(Й: Я)( Ц 25.8.9~. Но [(;1» ) ([Р». Поэтому (Й . Р) т; (Й . д) ~ -. [()» ( ~ . [Р» ( что н требовалось доказать. !гл. Ри 150 НОРМАЛЬНЫЕ АЛГОРИФМЫ СОКРАЩАЮЩИЕ АЛГОРИФМЫ 2. Пусть А — алфавит и 6А — нормальный алгорифм в алфавите А с сокращенно записанной схемой где $ пробегает алфавит А. Нормальный алгорифм 6А сокращающий.
Имеем поэтому 2.1. Алгврифм 6А применим ко всякому слову в алфавите А [1.2]. Далее, очевидно 2.2. Алгорифм 6А действует на всякое непустое слово в алфавите А. Докажем теперь, что 2.3. Алгорифм бх перерабатывает всякое слово в алфавите А в пустое слово. Пусть Р— слово в алфавите А. Имеется слово (е в А такое, что (1) бк(Р) ~ 9 [2.Ц. Имеем поэтому 6А . Р (= Я или 6А ..
Р )= 1,! ) . Первая возможность отпадает, так как заключительных формул подстановок в схеме 6А нет. Следовательно, 6А. Р)= Я '!. Отсюда следует, что (2) 1~ я. Л [2.2]. Таким образом, 6А(Р) мЛ[(1), (2)], что и требовалось доказать. Ввиду 2.3 мы будем называть алгорифм 6А аннулирую!цим алгорифмом в А. 3. Фиксируем слово С в алфавите А и обозначим 6А, с нормальный алгорифм в алфавите А со следукицей сокращенно записанной схемой: (':.. где $ пробегает А.
Алгорифм 6А, с сокращающий. Имеем поэтому 3.1. Алгорифм 6А. с применим ко всякому слову в алфавипм А [1.2]. 3.2. Алгорифм 6А с действует на всякое слово в алфавите А; если при этом слово Р в алфавите А непусто, то формула подстановки, активная на Р в 6А, с, простая. Из 3.2 следует 3.3. Невозможно естественное окончание процесса применения алгорифма 6А, с. 3.4. Если 6А. с. )с! — Я, то й ХЛ и Я мС. В самом деле, если Я непусто, то в силу 3.2 алгорифм 6А, с просто переводит Н в некоторое слово 5, что невозможно, так как по условию 6А, СЯ~ Я Поэтому Й~Л. Единственной формулой подстановки, действующей на Л, является формула С, ввиду чего 6А, с.
'Л) — С. Таким образом, () хС, что н требовалось доказать. 3.3. Ллгорифм 6А, с перерабатывает всякое слово в алфавите А в слово С. Пусть Р— слово в алфавите А. Имеется слово () в А такое, что (1) 6А, с(Р) ХЯ [3.1]. Имеем 6А, с' Р(= !е' или 6А. с! Р(=(е ~. Вторая возможность отпадает [3,3]. Следовательно, 6А, с. Р (= Я, и потому имеется слово Я такое, что 6А, с. Я) — Я. Отсюда следует, что (2) Я 'йс С [3.4].
Таким образом, 6А с(Р) мС [(1), (2)], что и требовалось доказать. 4. Фиксируем букву а алфавита А и обозначим ЗА,, нормальный алгорифм в алфавите А со схемой е$ — е е- где ~ пробегает алфавит А. Алгорифм ЗА,,— сокращающий. Имеем поэтому 4.1. Алгорифм ЗА,, применим ко всякому слову в алфавите А [1.2]. В следующих леммах буквы Х, У,, Р будут означать слова в алфавите А. Имеем 4.2. ЗА, 1' ( тогда и только тогда, когда г не входит в У. Пусть Р— слово, не содержащее е. Будем говорить о слове Х, что оно есть левое Р-слово, в следующих двух случаях: 1) когда а входит в Х и Р есть левое крыло первого вхождения з в Х; 2) когда Хя.Р.
Легко доказывается следующая лемма: 4.3. Если Х есть левое Р-слово и ЗА, Х! — У, то 1' есть левое Р-слово. Отсюда индукцией по шагам работы ЗА., [2 25.10, 327.3] получаем РАзветвляющии АлГОРНФм [гл, гн 152 НОРМАЛЬНЫЕ АЛГОРИФМЫ ф 301 4.4. Если Х есть левое Р-слово и ЗА вс Х|= У, то У еспгь левое Р-слово Докажем теперь 4.5. Алгорифм ЗА,, перерабатывает всякое левое Р-слово в Р. Пусть Х есть левое Р-слово. Алгорифм ЗА, применим к Х (4.Ц.
Имеется слово г в алфавите А такое, что ЗА,,(Х) .и. У. Так как схема алгорифма ЗА,, состоит из простых формул подстановок, имеем ЗА, Х)=У ~, и потому Здлй Х ~ 1' и ЗА, У ~. Следовательно, 1' есть левое Р-слово и е не входит в Г [4.4, 4.21. Поэтому 3'Х Р, что и требовалось доказать. Принимая во внимание определение левого Р-слова, мы можем переформулировать утверждение 4.5 следующим образом: 4.6. Алгорифм ЗА, перерабатывает всякое слово в алфавите А, не содержащее е, в это самое слово; он перерабатывает всякое слово Х в алфавите А, содержащее е, в левое крыло первого вхождения е в Х.
Обозначим ЕА, нормальный алгорифм в алфавите А со схемой где $ пробегает алфавит А.1 Последним вхождением слова Р в слово 1г будем называть такое вхождение К слова Р в слово Я, что всякое другое вхождение Р в 1г предшествует К. Аналогично 4.8 доказывается 4.7. Алгорифм ЕА,, перерабатывает всякое слово в алфавите А, не содержащее г, в это самое слово; он перерабатывает всякое слово Х в алфавите А, содержащее и, в правое крыло последнего вхождения в в Х, Пусть теперь г не является буквой алфавита А. Возьмем алфавит Ае и для него построим нормальные алгорифмы ЗА,, и ВА,, Вспоминая определение в-пары слов в алфавите А (2 22.31, видим, что 4.8. Какова бы ни была и-пара слов в алфавите А, алгорифм ЗА, е перерабатывает ее в первый элемент этой пары, а ал- гОРифМ Юде, е — ВО ВтОРОй. Ввиду 4.8 мы называем алгорифмы ЗА,, и ЮА,, в алфавите Ае отсекающими лгорифмами для алфавита А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
