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

Yechish: 
Bu algoritm quyidagi bitta formuladan iborat bo’ladi: {ba→ ab. P so’zda 
qatnashuvchi hech bo’lmaganda bitta “b” simvolining o’ng tomonida “a” simvoli 
mavjud bo’lsa, ushbu formula barcha “a” larni chap tomonga o’tkazadi. P kirish 
so’zidagi “b” simvollarining o’ng tomonida bitta ham “a” simvoli qolmasa, 
algoritm istalgan natijaga erishadi.
3-misol
. А={a,b} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. Bo’sh 
bo’lmagan P kirish so’zidagi birinchi simvolni o’chiruvchi , bo’sh kirish so’zini 
o’zgarishsiz qoldiruvchi algoritm tuzilsin.
Yechish: 
Algoritm kirish so’zidagi birinchi simvolni o’chirib, darhol ishini 
to’xtatishi kerak. Bunda quyidagi buyruqlardan foydalanish mumkin: 
Ammo algoritmning bunday tuzilishi to’g’ri emas. Bunga algoritmni bbaba kirish 
so’ziga qo’llab amin bo’lish mumkin: bbaba a bbba. Markovning normal 
algoritmi masala shartida talab qilingan birinchi simvolni emas, balki birinchi “a” 
simvolini o’chirdi. Demak algoritm faqat birinchi simvoli “a” bo’lgan kirish 
so’zlaridagina to’g’ri ishlaydi. Agar Markovning normal algoritmidagi buyruqlar 
ning joyini o’zgartirsak, algoritm faqat birinchi simvoli “b” bo’lgan kirish 
so’zlarida to’g’ri ishlaydi. Bu muammoni hal etish uchun kirish so’zidagi birinchi 
simvolni qandaydir usul bilan belgilab olish usulidan foydalaniladi. Masalan, 

---

belgilanuvchi simvol oldidan “*” simvoli joylashtiriladi. Buning uchun quyidagi 
formuladan foydalanish mumkin: → * . Endi Markovning normal algoritmi 
quyidagi ko’rinishni oladi: 
Ushbu algoritmning yuqorida keltirilgan bbaba kirish so’zi ustida ishlashini 
ko’raylik: 
 
bbaba → *bbaba → **bbaba → ***bbaba → … 
 
Ko’rinib turibdiki, bu kirish so’zi ustida algoritm cheksiz bajariladi. Bundan
muhim qoida kelib chqadi: agar Markovning normal algoritmi →β ko’rinishdagi 
chap tomoni bo’sh formulaga ega bo’lsa, bunday formula doimo Markovning 
normal algoritmi ning oxiriga joylashtirilish kerak. Agar (1) formulani 
Markovning normal algoritmi oxiriga o’tkazsak, u quyidagi ko’rinishni oladi: 
Ushbu algoritmni yana bir marta tekshirib ko’ramiz: bbaba → *bbaba a baba. 
Ushbu algoritm bo’sh kirish so’ziga ham qo’llaniluvchi bo’lish uchun uni yana 
bitta formula bilan to’ldiramiz: 

---

4-misol.
А={0,1,2,3} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. Agar P 
to’rtlik sanoq sistemasidan olingan so’z bo’lsa, uni ikkilik sanoq sistemasiga 
o’giruvchi algoritm tuzilsin. Masalan, 0123 → 00011011. 
Yechish
: To’rtlik sanoq sistemasidagi sonlarni ikkilik sanoq sistemasiga o’girish 
uchun sonda qatnashuvchi har bitta raqamni ikkilik sanoq sistemasiga o’girish 
kerak, ya’ni