Построить нормальный алгоритм, применимый ко всем словам x1x2…xn в алфавите {a,b} и переводящий их

Построить нормальный алгоритм, применимый ко всем словам x1x2…xn в алфавите {a,b} и переводящий их в слово α. Задание по вариантам представлено в таблице 8.1. Таблица 8.1 № вар. α 7 a*a, если n – нечетно, x1x2…xn-1nxn, если n – четно Задание Построить нормальный алгоритм, применимый ко всем словам x1x2…xn в алфавите {a,b} и переводящий их в слово: a*a, если n – нечетно, x1x2…xn-1nxn, если n – четно.

Последней в схеме подстановок запишем формулу →n. Тогда слово x1x2…xn перейдет в слово nx1x2…xn. Затем с помощью формул подстановок naa→aan, nab→abn, nba→ban, nbb→bbn символ n перейдет на конец слова: x1x2…xnn, если n – четно, или x1x2…xn-1nxn, если n – нечетно.
Для разбора случая n – нечетно введем следующие формулы подстановок (в случае n – четно они не сработают):
na→*, nb→*, a*→*, b*→*, *→a*a . .
Все символы удаляются справа налево и остаётся только символ *, который заменяется на требуемое слово a*a.
Для разбора случая n – четно введем следующие формулы подстановок (в случае n – нечетно они не сработают):
an→na., bn→nb

. .
Все символы удаляются справа налево и остаётся только символ *, который заменяется на требуемое слово a*a.
Для разбора случая n – четно введем следующие формулы подстановок (в случае n – нечетно они не сработают):
an→na., bn→nb