3-4-mavzu: Primitiv rekursiv funksiyalar. Tyuring tezisi. Markovning normal algoritmi

Eslatib o’taman 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:

Buning uchun algoritmga yana o’zgartirish kiritamiz:

Endi algoritm to’g’ri ishlaydi:
abbcabbca → abbabbca → abbabba → adddabba.

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.

E’tiboringiz uchun rahmat!