Ii-bob. Markovning normal algoritmlari 1 Normal algoritm tushunchasi va uning bajarilish qoidasi

0→00, 1→01, 2→10, 3→11.
Bularni Markovning normal algoritmi 
tiliga o’girsak, quyidagi algoritmga ega bo’lamiz: 
Ammo bu algoritm to’g’ri ishlamaydi. Bunga quyidagi kirish so’zini ushbiu 
algoritm vositasida qayta ishlashda amin bo’lamiz: 0123 → 00123 → 000123 →… 
Bu yerdagi xatolik shundan iboratki, to’rtlik raqamlarni ikkilik raqamlar bilan 
almashtirgandan keyin, ularni to’rtlik raqamlardan ajratib bo’lmaydi. Shuning 
uchun kirish so’zidagi almashgan raqamlarni hali almashtirilmagan raqamlardan 
qaysidir usul bilan ajratish kerak. Buning uchun quyidagicha ish qilish mumkin: 
almashtirilishi kerak bo’lgan raqamning chap tomoniga maxsus belgi qo’yiladi va 
almashtirish bajarilgandan keyin bu belgi navbatdagi almashtiriluvchi raqam 
oldiga joylashtiriladi va hokazo. 
0123 → *0123 → 00*123 → 0001*23 → 000110*3 → 00011011* 
Shunday qilib, “*” simvoli avval to’rtlik son birinchi raqamining chap tomoniga 
joylashtiriladi. Har bir almashuvdan keyin ushbu belgi o’ngga xarakat qilib, 
o’zining chap tonmonida ikkilik raqamlarni qoldirishi kerak. Algoritm “*” 
simvolining o’ng tomonida raqam qolmagach, to’xtaydi. Kirish so’ziga chapdan 
“*” simvolini qo’shish va uni o’chirish amallarini yuqoridagi misolda ko’rib 
o’tdik. “*” simvolini kirish so’zi simvollari bo’ylab chapdan o’ngga xarakat 
qildirish uchun *α→βγ* ko’rinishdagi formulasidan foydalaniladi. Bu erda α 

---

to’rtlik raqam, βγ esa unga mos ikkilik raqamlar jufti. Shunday qilib quyidagi 
ko’rinishdagi Markovning normal algoritmiga ega bo’lamiz: 
Ushbu algoritm ishini 0123 kirish so’zi uchun tekshirib ko’raylik:
5-misol
. А={a,b} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. P so’zning 
oxiriga “a” simvolini yozuvchi algoritm tuzilsin.
Yechish: 
Avvalo →a formula P so’zga chapdan a simvolini qo’shish uchun 
ishlatilishini eslatib o’tamiz. P so’zning o’ng tomoniga a simvolini qo’shish uchin 
uning oxirini belgilab olish kerak. Buning uchun “*” belgisini P so’zning oxiriga 
joylashtirib, so’ngra uni “a” simvol bilan almashtiramiz: P→…→P* Pa. 
Ammo “*” belgisini P so’zning oxiriga qanday joylashtirish mumkinq Buning 
ucnun “*” belgisi P so’zdan chapda joylashtirilib, barcha simvollardan oshirib 
o’tkaziladi va so’z oxiriga o’rnatiladi.: