В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 52
Текст из файла (страница 52)
д) абеабеаЬеаЬ» аЬаЬЬеабеаЬ» аЬаЬЬаЬЬеаЬ аЬаЬЬаЬЬаЬЬ. (Выделено то подслово, к которому на следующем шаге применяется соответствующая подстановка.) ж) аЬеаЬеаЬеаЬ» аЬеаЬеаЬ» аЬеаЬ =«аЬ. и) абеаЬеаЬеаб» абеабеаЬ» абеаб =«аб. к) аЬеабеаЬеаб» аеаЬеаЬ =«аеа. 14.5. Каждую из марковских подстановок задачи 14.4 примените к слову ЬеабеаЬеаЬеа максимально возможное число раз. 14.6.
Каждую из марковских подстановок задачи 14.4 примените к слову саЬеаЬеаЬеаЬ максимально возможное число раз. 14.7. Каждую из марковских подстановок задачи 14.1 примените к словам из задач 14.1 — 14.3 максимально возможное число раз. Нормальные алгоритмы н нх применение к словам.
Упорядоченная конечная совокупность марковских подстановок в алфавите А: Р, — «(.)Я, Рг -+ (')й Р, -+()Д„ определяет следующее правило построения последовательности И; (г = О, 1, 2, ...) слов в алфавите А, исходя из данного слова И«в этом алфавите, называемое нормальным алгорипииом (Ьгаркоеа) л ал4авипге А.
(Указанная совокупность марковских подстановок называется схемой или записью нормального алгоритма. Точка в скобках обозначает, что каждая из подстановок может быть заключительной.) В качестве начального слова И ь последовательности берется данное слово И; и говорят, что слово Иь получается из слова И'после нуля шагов переработки. Пусть для некоторого натурального г > 0 нам уже известно слово И~, полученное из )Р после г' шагов переработки, и процесс построения рассматриваемой последовательности еще не завершился. Тогда (1+ 1)-й шаг переработки будет состоять в следующем.
В схеме алгоритма ищем первую подстановку, левая часть Р которой есть подслово слова 250 И~, и затем в И"; вместо первого вхождения Р подставляем правое слово Д этой подстановки. Возникшее в результате подстановки слово обозначается через И";„. Если использованная для получения слова И;.,~ подстановка была простой, то говорят, что К,~ получено из слова И'; в результате 1+ 1 шагов переработки. Если же указанная подстановка была заключительной, то слово Им, называется результатом переработки слова И'посредством нормального алгоритма.
Может случиться, что в схеме нормального алгоритма не окажется ни одной подстановки, левое слово которой входит в качестве подслова в слово И'ь В этом случае полагаем И~м, = И; и также говорим, что И";„есть результат переработки слова И "посредством данного нормального алгоритма. В обоих последних случаях говорят, что процесс переработки слова обрывается после (1 + 1)-го шага. Если процесс переработки слова И' ни на каком шаге не обрывается, то говорят, что результат переработки слова И'посредством данного нормального алгоритма не определен. Мы определили понятие нормального алгоритма в алфавите А.
Если же алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над А. 14.8. Нормальный алгоритм в алфавите А = (а, Ь, 1) задается схемой: а-+ 1, Ь-+ 1. Примените его к слову: а) абабагс б) бабабЬаа; в) ааа; г) ЬЬЬЬ; д) аабЬЫ1; е) НааЬ; ж) ЬаааЫа; з) 111ааЫ; и) ааЬЬ; к) аЬЬЬа; л) аЬааЬЬЬ. Решение. л) Данный алгоритм сначала последовательно заменяет все вхождения буквы а в данном слове на букву 1, и затем также последовательно заменяет все вхождения буквы Ь на букву 1. Имеющиеся в слове буквы 1 оставляет без изменения.
Таким образом, данное слово перерабатывается в слово, состоящее из такого количества единиц, сколько всего букв содержало данное слово. Процесс переработки данного слова выглядит так: аЬааЬЬЬ ~ ~ 1бааббб ~ 1ЫабБЬ ~ 1ЬПЬЬЬ ~ 1 ЕПЬЬЬ ~ 11111ЬЬ => 111111Ь => ~ 1111111. К полученному слову ни одна из подстановок данной схемы уже не применима. Следовательно, работа алгоритма завершена. 14.9. Нормальный алгоритм в алфавите А = (а, Ь, Ц задается схемой: а -+ 1, Ь -+ 1, 11 -+ Л. Примените его к словам из предыдушей задачи.
Р е ш е н и е. л) Алгоритм предыдущей задачи является составной частью алгоритма настоящей задачи. Поэтому вначале данное слово перерабатывается в слово, состоящее из такого количества единиц, сколько всего букв содержит данное слово. Затем в полученном слове из единиц начинают вычеркивать единицы по две штуки. В итоге либо не останется ни одной единицы (пустое слово, если исходное слово содержало четное число букв), либо остается одна единица. Например, для рассматриваемого слова процесс переработки выглядит так (с учетом работы алгоритма из 251 предыдущей задачи): аЬааЬЬЬ => 1111111 =~ 11111 = 111 => 1. К полученному слову ни одна из подстановок данной схемы уже не применима.
Следовательно, работа алгоритма завершена. 14.10. Нормальный апгоритм в алфавите А = (а, Ь) задается схемой: Ьа -+ аЬ, аЬ -+ Л. Примените его к словам: а) ЬаЬааа; б) ааЬЬдаЬ; в) аЬааЬЬ; г) ЬЬЬЬ; д) ааЬЬЬаа; е) ааЬаа'„ж) ЬЬЬааа; з) ЬааЬЬааЬ; и) дЬЬаЬЬа; к) ЬЬааЬаЬ. Выявите закономерность в работе алгоритма. Решен не. к) Сначала возможное число раз работает первая подстановка схемы: ЬЬадЬаЬ => ЬаЬаЬаЬ => аЬЬаЬаБ ~ аЬаЬЬаЬ ~ ~ ааЬЬЬаЬ => ааЬЬаЬЬ => ааЬаЬЬЬ ~ аааЬЬЬЬ. Первая подстановка себя исчерпала и к полученному слову более не применима. Но теперь работает вторая подстановка: аааЬЬЬЬ ~ ааЬЬЬ ~ аЬЬ => Ь.
14.11. Нормальный алгоритм в алфавите А = (а, Ь) задается схемой: аЬ -+ Л, Ьа -+ аЬ. Примените его к словам из предыдущей задачи. Р е ш е н и е. л) Настоящий алгоритм отличается от предыдущего порядком выполнения подстановок. Тем не менее в итоге он приводит к тому же результату, что и алгоритм предыдущей задачи: ЬЬааЬаЬ => БЬааЬ ~ ЬЬа ~ ЬаЬ = Ь. Аналогична ситуация и со всеми остальными словами из предыдущей задачи.
14.12. Нормальный алгоритм в алфавите А = (а, Ь) задается схемой: аЬ -э а, Ь -+ Л, а -+ Ь. Примените его к следующим словам: а) ЬЬааЬ, б) ааЬЬЬаа; в) ЬаЬаЬаЬ; г) аааа; д) ЬЬЬЬЬ; е) ааЬааЬЬ; ж) аЬЬЬЬЬа; з) ЬааЬ; и) ЬЬЬааа; к) аЬЬаЬЬа; л) аЬЬЬаааЬ.
Р е ш е н и е. л) Проанализируйте работу данного алгоритма на данном слове, обосновав каждый его шаг: аЬЬЬаааЬ ~ аЬБаааБ => ~ аЬаааБ ааааЬ => аааа ~ Ьаад => ааа ~ Ьаа => аа ~ Ьа ~ а => Ь => => Л. Убедитесь в том, что данный алгоритм каждое слово перерабатывает в пустое. 14.13. Изменим немного алгоритм из предыдущей задачи: аЬ -э -+ а, Ь -+ . Л, а -+ Ь. Примените его к тем же словам.
Ре ш е н и е. л) аЬЬЬаааЬ => аЬБаааЬ ~ аЬаааБ ~ ааааЬ => аааа => ~ Ьааа ~ ааа. На последнем шаге применена заключительная подстановка Ь -+ . Л, чем и завершилась работа алгоритма. 14.14. Примените к словам из задачи 14.12 нормальный алгоритм со схемой: Ьа -+ аЬ, а -+ Л, Ь -+ . Ь. 14.15. Примените к словам из задачи 14.12 нормальный алгоритм со схемой: аЬ-+ Ь, Ьа-+ ЬЬ, Ь-+. Л.
14.16. Примените к словам из задачи 14.12 нормальный алгоритм в алфавите А = (а, Ь) со схемой: Ьа -+ а, ЬЬ вЂ” ~ Ь, аЬ -+ Л, Л -+ -Ф. Б. 14.17. Примените к словам из задачи 14.12 нормапьный алгоритм со схемой: БЬ -+ Ьа, Ьа -+ а, а -+ Л, Ь -+ . Л. Убедитесь, что каждое слово в алфавите А = (а, Ь) он перерабатывает в пустое. 252 14.18. Примените к словам из задачи 14.12 нормальный алгоритм в алфавите А = (а, Ь) со схемой: ЬЬ -+ ба, Ьа -+ а, а -+ Л, Л -+ . Ь. 14.19. Нормальный алгоритм в алфавите А = (а, Ь, с, с() задается схемой: аН-+ . Ис, Ба -+ Л, а -+ Ьс, Ьс -+ БЬа, Л вЂ” ~ а. Примените его к следующим словам: а) йсб; б) Ибс; в) Бсй; г) сааб; д) г?асб; е) с(ас; ж) Нса; з) Ьаа1; и) Иабс; к) сйба; л) Ыс. Решение.
л) Укажите, какие использованы подстановки на каждом шаге работы алгоритма: Ьйс = аЫс => Бсбс?с ~ БбаЫс => ~ Ббдс => аЬЫс ~ БсбЫс => Ббаббс?с ~ ЬЬЫс и т.д., т.е. алгоритм будет до бесконечности приписывать слева букву Ь, т.е. будет работать вечно. Это означает, что к данному слову он не применим. Нормально вычислимые функции. Рассматриваются числовые функции, т.е. функции заданные и принимающие значения в множестве натуральных чисел. Натуральные числа кодируются словами в алфавите А = (Ц, так что рассматриваются функции, заданные на словах над этим алфавитом. При этом будем говорить, что функция 7; заданная на некотором множестве слов алфавита А, нормально вычислима, если найдется такое расширение В данного алфавита (А ~ В) и такой нормальный алгоритм в В, что каждое слово Р (в алфавите А) из области определения функции /' этот алгоритм перерабатывает в слово ~(Р) (в алфавите А).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
