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

Yechish: 
Avvalo, shuni eslatib o’tishimiz kerakki, Markovning normal 
algoritmida simvollarni so’zga qo’shish va so’zdan o’chirish (olib tashlash) 
Tyuring mashinasidan farqli ravishda oson amalga oshiriladi. Bunda yangi 
simvollarni so’zga qo’shish – qandaydir qism so’zni simvollar soni ko’proq 
bo’lgan qism so’z bilan almashtirish yo’li bilan bajariladi. Masalan, bb→ddd
formulasi vositasida ikki simvol uch simvol bilan almashtiriladi. Buning uchun 
qoshimcha simvollarga joy ajratishga ehtiyoj sezilmaydi. Markovning normal 
algoritmida simvollar avtomatik holda suriladi. Simvollarni o’chirishda esa 
qandaydir qism so’z simvollar soni kamroq bo’lgan qism so’zga almashtiriladi. 
Masalan, “c” simvolini o’chirish c→ (o’ng qismi bo’sh formula) formula bilan 
bajariladi. Bunda so’z ichida hech qanday bo’sh o’rinlar paydo bo’lmaydi. 
Yuqoridagi mulohazalarga asoslangan holda berilgan masalani quyidagi 
Markovning normal algoritmi hal etish kerakdek tuyuladi: 

---

Ammo unday emas. Ushbu algoritmni abbcabbca kirish so’zi uchun tekshirib 
ko’raylik: 
Yozuvdan ko’rinib turibdiki, algoritm birinchi bb qism so’zni ddd qism so’zga 
almashtirib, c simvollarini o’chirishga o’tmadi,balki qolgan bb qism so’zlarni ham 
almashtirishda davom etdi. Nima sababdan? Eslatib o’tishimiz kerakki, 
Markovning normal algoritmining har bir qadamida o’rin almashtirish formulalari 
doimo yuqoridan pastga ko’rib chiqilib, birinchi formula kirish so’ziga 
qo’llaniluvchan bo’lgan holda qolgan formulalarga murojaat to’xtatilib turiladi. 
Shuning uchun Markovning normal algoritmi formulalarining yozilish tartibi 
muhim ahamiyat kasb etadi. Bundan kelib chiqib, formulalarning joyini 
almashtiramiz: 
Bu algoritmni yana oldingi tekshirilgan kirish so’zi uchun qo’llaymiz: 
Bu algoritm oldin ishlaganda kirish so’zidagi barcha c simvollarini o’chirib, 
so’ngra bb qism so’zlarini ddd qism so’zlariga almashtiradi. Birinchi bb → ddd 
almashuvdan keyin jarayonni qanday to’xtatish mumkin? Buning uchun 
algoritmga yana o’zgartirish kiritamiz: 
Endi algoritm to’g’ri ishlaydi: abbcabbca → abbabbca → abbabba → adddabba.

---

Algoritmni bb qism so’z qatnashmaydigan kirish so’zi uchun tekshirib ko’ramiz:
dcacb → dacb → dab. Bunda ikkinchi formula kirish so’ziga qo’llanilmas 
bo’lganligi uchun birinchi formula o’z ishi tugatgan paytdagi kirish so’zining 
holati chiqish so’zi yoki natija deb hisoblanadi. 
2-misol
. А={a,b,c,d} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. P kirish 
so’zida qatnashuvchi “a” simvollarini so’zning boshiga, “b” simvollarini so’zning 
oxiriga joylashtiruvchi Markovning normal algoritmi tuzilsin. Masalan, babba → 
aabbb.