Tatu samarqand filiali

6-laboratoriya ishi 
Mavzu: Tabiiy Markov algoritmlari 
Ishdan maqsad:
Tabiiy Markov algoritmlarini o’rganish. 
Qo’yilgan masala:
Topshiriq variantida berilgan masalani berilgan 
tuzilishdagi algoritmlar yordamida yechish. 
Qisqacha nazariy ma’lumot 
Ma’lum bir alifboga asoslangan algoritmik so’zlarning sinfi sobiq sovet matemategi 
A.A.Markov tomonidan tabiiy markov lagoritmi (TMA) nomi ostida ishlab chiqilgan. Har bir 
algoritm
Нормальные алгоритмы Маркова (далее — НАМ), введенные советским математиком 
А. А. Марковым, представляют собой класс алгоритмов, применимых к словам 
некоторого алфавита. Каждый НАМ определяется указанием алфавита, в котором он 
действует, и схемы НАМ. Алфавитом НАМ может служить любой конечный алфавит 
A
. 
Формулой подстановки в алфавите 
A
называется выражение типа 
p
→ 
q
(простая 
подстановка, в эмуляторе обозначена как ->) или 
p
↦
q
(заключительная подстановка, в 
эмуляторе обозначена как =>), где 
p
и 
q
— некоторые слова в алфавите 
A
, называемые, 
соответственно, левой и правой частями формулы подстановки. Каждый НАМ в алфавите 
A
имеет конечное число формул подстановки. Их записывают в виде списка, который 
называется схемой алгоритма.
Применение НАМ к некоторому слову 
S
заключается в следующем. В списке формул 
подстановки ищется первая из тех формул, в которой левая часть входит в 
S
. Находится 1-
е вхождение левой части формулы в 
S
и вместо этого вхождения подставляется правая 
часть формулы. Получается новое слово 
S
'
. Cо словом 
S
'
производятся те же действия и 
т.д.
Данный процесс обрывается в 2-х случаях:

к очередному слову применена одна из заключительных формул подстановки;

в слово не входит ни одна из левых частей формул подстановки. 
Получаемое последнее слово является результатом применения НАМ к исходному слову 
S
.
Примеры на составление нормальных алгоритмов Маркова