Т. А. Сливина математическая логика и теория алгоритмов

Пример 1. Пусть А есть алфавит {b,c} . Рассмотрим схему
b
сc.
Определяемый этой схемой нормальный алгоритм U перерабатывает всякое слово Р в алфавите А, содержащее хотя бы одно вхождение буквы b, в слово, которое получается вычеркиванием в Р самого левого вхождения буквы b.
Действительно, всякая буква с, находящаяся в слове левее самой левой буквы b, простой подстановкой с с переводится в букву с, а самая левая буква b заключительной подстановкой переводится в пустое слово .
Например, если Р = ссbbс, то PQ, где Q = ссbс.
Пустое слово U перерабатывает в само себя.
U не применим к непустым словам, не содержащим вхождения буквы b. Действительно, если слово Р содержит только буквы с, то простой подстановкой с с оно будет перерабатываться в себя, но тогда всегда Р Р, и мы не приходим к заключительной подстановке, т.е. процесс будет продолжаться бесконечно.
Пример 2. Пусть А есть алфавит { a₀, a₁,…, a_n}. Рассмотрим схему
i (a_i) (a_iA).
Эта схема определяет нормальный алгоритм U, перерабатывающий всякое слово в алфавите А в пустое слово. Например,
U: a₁a₂a₁a₃a₀ ├ a₁a₂a₁a₃ ├ a₂a₁a₃ ├ a₂a₃ ├ a₃ ├ 
и, наконец,
U: . Следовательно, U(a₁a₂a₁a₃a₀) = .