Математическая логика и теория алгоритмов

пустого слова (Л) в Ro слово Р по 5), имеем pi?o- Если первой в Ro стоит буква а, то применяем подстановку 1), если же первая буква - Ь, то применяем подстановку 2), а если первая с , то применяем 3) и перемещаем (3 за первую букву в слове R q . Повторяя этот процесс столько раз, сколько букв в слове RQ , получим i?oP- По подстановке 4) окончательно имеем Roa, т.е. этот алгоритм приписывает к произ­ вольному слову RQ В алфавите А справа от RQ букву а. В рассмотренном алгоритме Б подстановки 1), 2) и 3) служат для перестановки местами р и а или р и 6 или р и с , т.е. для перестановки р с любой буквой алфавита А . Тогда можно ввести для нашего алгоритма В более краткую форму записи: Рх -> хР { х е А ) \*) В'=- ^ (в)а 2*) Л -> р 3*) Здесь запись (1*): Рх д:р применена для обозначения подстановок 1)-3) в 5 . Пусть A={ai,a2,---,a „} Р, <2 и i? - слова в алфавите А . Догово­ римся, что запись вида PxQ ( » ) R( х е А ) обозначает таблицу подстановок; PoiQ ( »)R PaiQ -> {»)R P^nQ - > ( ® ) ^ 3. Пусть заданы алфавиты A wВ, буква a не входит в А п в В и аьаъ-'.йк - фиксированные буквы из алфавита А, а Q],Q2,-,Qk - фиксированные слова в алфавите В. Рассмотрим нормальный алгоритм в алфавитеЛи5и{а} , задаваемый таблицей аа,- g,a (i=\,2,...k) (XX ха Xе A\{ai,a2,--)(^k} В—{ а -> • Л Л -> а 223