Amaliy matematika va informatika kafedrasi



Download 251,8 Kb.
bet12/26
Sana31.12.2021
Hajmi251,8 Kb.
#228816
1   ...   8   9   10   11   12   13   14   15   ...   26
Bog'liq
Asliddin kurs ishi

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.


Download 251,8 Kb.

Do'stlaringiz bilan baham:
1   ...   8   9   10   11   12   13   14   15   ...   26




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish