Amaliy matematika va informatika kafedrasi

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