Amaliy matematika va informatika kafedrasi

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.: