Ii-bob. Markovning normal algoritmlari

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