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

Quyida Markovning normal algoritmlari tuzishda foydalaniladigan bir qancha tipik usullarni namoyish qiluvchi misollarni ko’rib o’tamiz. Bu misollarning berilishida ishlatiladiga ba’zi belgilashlarni izohlab o’tamiz. A harfi bilan kirish so’zi alfaviti, ya’ni kirish so’zida qatnashishi mumkin bo’lgan simvollar to’plami ifodalanadi. P harfi bilan kirish so’zining o’zi belgilanadi.Bundan tashqari, o’rin almashtirish formulalaridan o’ng tomonda ularning tartib raqamlari ham ko’rsatiladi. Bu raqamlar formulalar tarkibiga kirmaydi, ammo Markovning normal algoritmlarini qadamma-qadam bajarilishini izohlashda ushbu tartib raqamlari zarur bo’ladi.

1-misol. А={a,b,c,d} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. P kirish so’zining bb birinchi (chapdan) qism so’zini ddd qism so’zga almashtiruvchi va undagi barcha c qism so’zlarni o’chiruvchi Markovning normal algoritmi tuzilsin. Masalan: abbcabbca → adddabba

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.

Yuqoridagi mulohazalarga asoslangan holda berilgan masalani quyidagi Markovning normal algoritmi hal etish kerakdek tuyuladi:

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

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.