Решение алгоритмов Маркова

НАМ получается слишком громоздким (56 правил). Так что вот тебе для алфавита {a, b, c}, а для остальных букв по этому же шаблону сам допишешь:

 aA → Aa

bA → Ab

cA → Ac

aB → Ba

bB → Bb

cB → Bc

aC → Ca

bC → Cb

cC → Cc

A ↦ a

B ↦ b

C ↦ c

#a → a#

#b → b#

#c → c#

a# -> A

b# -> B

c# -> C

# ↦

→ # 

Символ ↦ обозначает команду "заменить и завершить работу"

Для начала необходимо определиться с форматом входных и выходных данных. Входными данными должна быть строка из символов алфавита A, а выходными - та же строка, но со сдвигом вправо.

Для реализации алгоритма Маркова необходимо создать два состояния: начальное и конечное. На начальном состоянии входная строка будет передана на вход программы. Затем мы будем двигать символы строки вправо, переносить последний символ в начало. Когда достигнем конечного состояния, программа завершится и вернет измененную строку.

Алгоритм можно описать следующим образом:

• Создать начальное состояние - прочитать входную строку.
• Установить счетчик на 1.
• Перенести последний символ в строке в начало.
• Если счетчик равен длине строки, то перейти на конечное состояние.
• Иначе, увеличить счетчик на 1 и перейти на шаг 3.
• Создать конечное состояние - вернуть измененную строку.

Пример реализации алгоритма на языке Python:

 

def markov_algorithm(input_string): 

    length = len(input_string) 

    # начальное состояние 

    state = input_string 

    i = 1 

    while i

 aA → Aa

bA → Ab

cA → Ac

aB → Ba

bB → Bb

cB → Bc

aC → Ca

bC → Cb

cC → Cc

A ↦ a

B ↦ b

C ↦ c

#a → a#

#b → b#

#c → c#

a# -> A

b# -> B

c# -> C

# ↦

→ #