Данный алгоритм удаляет все буквы а в произвольном слове, например . Выполнение алгоритма завершилось, так как формула невыполнима для слова bbc.
Пример 2. Алфавит {а, b, c}. Нормальный алгоритм:
a
Данный алгоритм приписывает к началу слова букву а, и его работа завершается, например, .
Пример 3. Алфавит {а, b, c}. Нормальный алгоритм:
→a
Данный алгоритм неприменим ни к одному слову, так как его исполнение бесконечно, поскольку пустой текст существует в любом слове, например, .
Пример 4. Дано слово в алфавите {a, b, c}. Приписать к слову справа букву а.
Например, из слова ababc надо получить слово ababca.
Замечание. В отличие от машины Тьюринга, которая имеет возможность передвижения вдоль слова к любой его части, нормальный алгоритм имеет возможность передвижения только к левому концу текста, поэтому доступ к правому концу необходимо смоделировать в самом алгоритме.
Введем дополнительный символ *, не входящий во внешний алфавит, и будем им помечать интересующее место в слове.
Последовательность действий Соответствующие формулы подстановок
1) приписать слева к слову символ * →*
2) передвижение * на правый конец слова *a→a*
*b→b*
*c→c*
3) замена * на а * a
Если указать формулы подстановки именно в такой последовательности, то исполнение алгоритма зациклится на выполнении первой формулы. Чтобы этого не произошло, поместим ее в конец алгоритма, после формулы завершающего типа
1) *a→a*
2) *b→b*
3) *c→c*
4) * a
5) →*
Так как входное слово состоит из символов алфавита {a, b, c}, то все остальные формулы на первом такте окажутся невыполнимыми, и, следовательно, последовательность действий не нарушится:
Пример 5. Составить нормальный алгоритм вычисления функции f(x)=x + 1.
Будем работать с числами, записанными в троичной системе счисления, т. е. со словами в алфавите {0, 1, 2}.
1) *0→0*
2) *1→1*
3) *2→2*
4) *→#
5) 0# 1
6) 1# 2
7) 2#→#0
8) # 1
9) →*
Проиллюстрируем работу алгоритма на примерах.
1. Входное слово – число 1023
2. Входное слово – число 223
В некоторых случаях (примеры 4, 5) не удается построить нормальный алгоритм, эквивалентный данному в алфавите А, если использовать в подстановках алгоритма только символы данного алфавита. Однако можно произвести расширение алфавита. В этом случае говорят, что построенный алгоритм является алгоритмом над алфавитом А, хотя он будет применяться только к словам из А.
Сформулируем два достаточных признака применимости нормального алгоритма к любому входному слову:
1) во всех формулах подстановок левые части непустые, а в правых нет тех символов, которые встречаются в левых частях (гарантирует отсутствие зацикливания, так как в конце концов все формулы станут невыполнимы);
2) в каждой формуле подстановки правая часть короче левой (гарантирует уменьшение длины слова).
Loading ...