Ii-bob. Markovning normal algoritmlari

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.
   

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.