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