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

Question

1. Построить нормальный алгоритм, применимый ко всем словам x1, x2, xn в алфавите {а, b} и переводящий их в слово (b^n) х1. хn
 
2. Проверить работу построенного нормального алгоритма над некоторыми словами.

Answer 1

1. Нормальный алгоритм

Вход: Слово x1x2. xn в алфавите {a, b}
Выход: Слово (b^n) x1x2. xn

Алгоритм:

1. Написать n копий буквы b.
2. Конкатенировать эти копии с входным словом.

Пример:

Для входного слова ab алгоритм сработает следующим образом:

1. Пишем две копии буквы b: bb.
2. Конкатенируем копии с входным словом: bb ab.
3. Выходное слово: bb ab.

2. Проверка работы алгоритма

Входное слово | Выходное слово
- | -
ab | bb ab
baa | bbb baa
abab | bbbb abab
bb | bbbb bb