Дана алфавит 𝐴 = {𝑎, 𝑏}. Удвоить слово 𝑅, то есть приписать слева или справа его копию. Например, 𝑎𝑏𝑏 ⟶ 𝑎𝑏𝑏𝑎𝑏𝑏. Чтение слова начинается слева. Написать алгоритм Маркова.

Ниже приведён один из вариантов марковского алгоритма для удвоения слова над алфавитом A = {a, b}, то есть для преобразования слова R в RR. Идея алгоритма такова: мы «подклеиваем» копию входного слова R к его правому краю. Для этого удобно пометить начало исходного слова специальным символом (например, «*») и затем, проходя слева направо, переносить каждую букву, стоящую сразу после звезды, в конец строки (при этом сама буква остаётся на своём месте). В конце звезда удаляется, и получается слово вида R R. Общий план решения: 1. Подготовка. В предположении, что исходное слово R читается слева ...