Markov (yoki normal) algoitmlar

Ta'rifi
- A
Markov Algoritmi
cheklangan ketma-ketlikdir P
1
, P
2
,..., P
n
ning
Markov productions
quyidagi qoidalarga muvofiq berilgan alifbodagi satrlarga qo'llanilishi kerak. Ruxsat bering S berilgan satr
bo'ling. Birinchi
ishlab chiqarishni topish uchun ketma-ketlik qidiriladi P
men
agar bunday
ishlab chiqarish mavjud bo'lmasa, algoritmning ishlashi o'zgarishsiz to'xtaydi S. agar algoritmda avvalgisi
sodir bo'lganishlab

---

CSE 6390e hisoblash tilshunosligi
2
chiqarish mavjud bo'lsa S, birinchi bunday ishlab chiqarish
qo'llaniladi
to S.agar bu yakuniy ishlab chiqarish bo'lsa, algoritmning ishlashi
S. da qo'shimcha o'zgarishsiz to'xtaydi, Agar bu oddiy ishlab chiqarish bo'lsa,
s' satr yordamida yangi qidiruv o'tkaziladi. Agar algoritmning ishlashi oxir
-oqibat satr bilan to'xtasa S*, biz buni aytamiz S * bo'ladi
natija
misol:
{a, b, c, d} bo'lishi alifbo oling. Algoritm quyida keltirilgan.
Algoritm M1
M11: [oxirgi] a d
→
* d c
M12: [oddiy]
b a →
W
M13: [oddiy]
a →
b c
M14: [oddiy]
b c →
b b a
M15: [oddiy]
W →
a
S = "dcb" ni olib, biz algoritmni qo'llaymiz
M15 tomonidan dcb adcbga aylanadi
M11 tomonidan adcb dccb bo'ladi va to'xtaydi.
S = "dbc" ni olib, biz algoritmni qo'llaymiz
M14 tomonidan DBC abba bo'ladi
M12 tomonidan abba JBga aylanadi
M15 db tomonidan OTB bo'ladi
M11 tomonidan OTB dcb bo'ladi va to'xtaydi.
S = "bdc" ni olib, biz algoritmni qo'llaymiz
M15 - abdc tomonidan, M13 - bcbdc tomonidan,
M14 - bbabdc tomonidan,M12-bbdc tomonidan ,
M15 - abbdc tomonidan,M13 - bcbbdc tomonidan,
M14 - bbabbdc tomonidan,
M12 - bbbdc tomonidan,
M15 - abbbdc tomonidan,...
Algoritmning ishlashi shu nuqtada to'xtamadi va BDC
ga tatbiq etilganda algoritm to'xtovsiz ishlaydi va b shaklining uzunroq va uzunroq satrlarini hosil qiladi...bdc.
Yuqoridagi misoldagi algoritmning maqsadi yo'q. Ammo Agar Markov algoritmi tushunchasi
foydali bo'lishi kerak bo'lsa, biz ushbu algoritmlar yordamida mazmunli vazifalarni bajarishimiz mumkinligini
ko'rsatishimiz kerak.
Misol:
alifbo belgilanmagan bo'lsin va a ushbu alifboda sobit qator bo'lsin. Biz
o'zboshimchalik bilan s qatorini as qatoriga aylantirmoqchimiz. Bu osonlik bilan quyidagilar bilan amalga oshiriladi.
Algoritm M2
M21: [oxirgi] Vt
→
* A
barcha vazifalarni bajarish oson emas. Masalan, biz S ni AS ga emas,
balki SA ga aylantirishni xohladik deylik. Biz algoritm m2 foydalana olmaysiz, bu keyingi ilovalar
sifatida satrlari ishlab chiqaradi uchun, AAS, AAAS,... Algoritmni S deb ham yoza olmaymiz
→ *SA, uchun hech
birinchi ishlab chiqarish bilan juda ko'p ishlab chiqarish bo'lishi kerak edi. Aslida, ishlab chiqarishlar har doim
A ning b ning birinchi paydobo'lishiga nisbatan qo'llanilganligi sababli, biz ikkinchi, uchinchi yoki oxirgi hodisa bilan
ishlashni xohlagan vaqtda qiyinchilik tug'diradi
. Biz ushbu alifboning bir qismi bo'lmagan maxsus marker belgilaridan foydalanishni joriy etish orqali ushbu qiyinchilikni
engamiz
. Ushbu markerlardan foydalanib, biz ma'lum bir nuqtani ip bilan belgilashimiz va
shu nuqtada ular ustida ishlashimiz mumkin.
Misol:
a bo'lsin
marker
alifboda emas. Agar S alfavitdagi satr, algoritmni qo'llash natijasi M3
ga S satr SA.
Algoritm M3
M31: [almashinuvi]
→
δβ
alphabet-ning bir a'zosi bo'lgan.
M32: [oxirgi]
→
*A
M33: