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

.  

Примеры на составление нормальных алгоритмов Маркова