Markov (yoki normal) algoitmlar

W →
β
Chunki S dastlab emas, o'z ichiga β, uchinchi chiqarish hisoblanadi, keyin foydalanish uchun harakat β o'tgan
ramzlari yilda S. Agar S o'z ichiga oladi n o'zgartirmay davlat ramzlari, keyin, so'ng, n qadamlar biz unga
string
Sβ. Bu vaqtda birinchi ishlab chiqarish endi amal qilmaydi, ikkinchi ishlab chiqarish
esa SAishlab chiqaradi. Ushbu ishlab chiqarish yakuniy bo'lganligi sababli, satr SA keyin natijadir.
Oldingi misolda biz yangi yozuvni kiritdik. Ya'ni, birinchi ishlab chiqarishda biz
alfavitdagi belgilar ustidan o'zgarib turadigan o'zgaruvchidan foydalandik. Shunday qilib, birinchi qator aslida
ishlab chiqarish emas, aksincha
ishlab chiqarish sxemasi
uchun alifbo belgilarini almashtirish orqali olinishi mumkin bo'lgan barcha
ishlab chiqarishlarni bildiradi
.
Markov algoritmlaridan foydalanish uslubi tufayli ishlab chiqarishni

---

CSE 6390e hisoblash tilshunosligi
3
yozish tartibi juda muhimdir. Agar m3 algoritmining dastlabki ikkita satri almashtirilgan bo'lsa, natijada
s ni SA ga emas, balki AS ga va ishlab chiqarishlarga aylantirish bo'ladi.
→ hech qachon foydalanilmaydi. Ishlab
chiqarish sxemasida buyurtma juda muhim emas. Bir oz fikr sizni ishlab chiqarish
sxemasi algoritmning alohida ishlab chiqarishlar tartibi qo'llaniladigan bo'limlarini ifodalashiga ishontirishi kerak va
ularning barchasi bir xil narsani, turli kontekstlarda bajaradi.
Biz ushbu bo'limni Markov algoritmlari tomonidan bajarilishi mumkin bo'lgan bir nechta vazifalar misollari bilan
yakunlaymiz
. Ushbu mavzuning rivojlanishi ushbu kirishdan ancha ustundir. Xususan,
liberal ma'noda algoritmlardan foydalanish orqali bajarilishi mumkin bo'lgan har qanday vazifani Markov
bajarishi mumkin algorithm.
In quyidagi misollar alifbo aniqlanmagan holda qoldiriladi, faqat unda
aniq ko'rsatilgan markerlar yoki maxsus belgilar mavjud emas.
Misol:
Ushbu algoritm har bir satrni bo'sh satrga aylantiradi.
Algoritm M4
M41: [ishlab chiqarish sxemasi]→ Wδ
ishlayotgan alifbo a'zosi
ushbu algoritm ketma-ket har qanday harf qolsa, satrning birinchi harflarini olib tashlaydi
. Ip bo'sh satrga aylanganda, jarayon to'xtaydi, chunki
avvalgi bo'sh satr bo'lgan transformatsiya mavjud emas.
Misol:
ushbu algoritm bo'sh satrni o'zgarishsiz qoldiradi, lekin bo'sh bo'lmagan satrning birinchi harfini o'chiradi va
to'xtaydi. Marker: O'zRTXB.
Algoritm M5
M51: [prod. sxema] ni ishlab chiqish
→
•W
alfavit bo'yicha O'zRTXB a'zosi
M52:
β →
•W
M53:
W →
misol:
ko'pincha satrdagi belgilar sonini bilish foydalidir. Bu
har bir belgini yorliq belgisi bilan almashtirish orqali osonlikcha amalga oshiriladi. Maxsus belgi: 1.
Algoritm M6
M61: [prod. sxema]
δ → 1 alfavitning o'qituvchi a'zosi
"1" alifbo elementi emasligi sababli, har bir belgi o'zgartirilganda operatsiya to'xtaydi.
Misol:
ba'zida kimdir simvol satrining bir qismini tashlashni xohlaydi, chunki javobni hisoblagandan so'ng ma'lumotlarni bekor
qiladi. Quyidagi algoritm hamma narsani maxsus belgining chap tomoniga tashlaydi.
Algoritm M7
M71: [prod. sxema]
δβ
→ β
alfavit bo'yicha O'zRTXB a'zosi
M72:
β
→ *V
misol:
deyarli har bir muammoda shu paytgacha hisoblash natijalariga bog'liq ravishda qaror qabul qilinishi kerak bo'lgan ba'zi
bir nuqta mavjud
. Endi biz bunday qaror qabul qilish uchun Markov algoritmini taqdim etamiz. Berilgan
alfavitdagi o'zboshimchalik bilan satr belgilangan satr ekanligini aniqlash uchun tekshiriladi A.Agar shunday bo'lsa,
butun satr b satr bilan almashtiriladi; aks holda butun satr satr bilan almashtiriladi C.Marker:
bitik.
Algoritm M8
M81:
δβ → βδ
alfavit bo'yicha O'zRTXB a'zosi
M82:
βδ → β
M83:
β → *C
M84:
Birδ→ β
M85:
A → β
M86:
A → *B
M87:
W → β
Agar berilgan satrda, P, satrning paydo bo'lishini o'z ichiga olmaydi a, oxirgi ishlab chiqarish a ni kiritadikatta ishlab
chiqarish sxemasi
va keyin ikkinchi va uchinchi ishlab chiqarish sxemasi o'chiriladi P va uni bilan almashtiring C.Agar P
ning paydo bo'lishini o'z ichiga oladi A, lekin emas a, yoki to'rtinchi yoki beshinchi ishlab chiqarish sxemasi joriy etish
uchun ishlatiladi; birinchi

---

CSE 6390e hisoblash tilshunosligi
4
sxema harakat qiladisekspning chap uchiga va keyin ikkinchi va uchinchisi avvalgidek ishlaydi. Va nihoyat, agar
satr P aslida a, oltinchi ishlab chiqarish amal qiladi va P ga aylantiriladi B.e'tibor bering
, ishlab chiqarishlar M8 to'g'ridan-to'g'ri torga murojaat qiling a, bu juda uzun bo'lishi mumkin. A apriori ma'lum beri, bu
joizdir: biz har doim a uchun xat qidirish uchun bir harf bilan bunday mos yozuvlar o'rniga
mumkin.misol:
juda keng tarqalgan yana bir tartibi takrorlash yoki mag'lubiyatga ko'paytirish, deb. Ko'pincha biz
mag'lubiyatga halok o'zgarishlarni amalga oshirish uchun xohish, lekin tabiatda faqat taxminiy bo'lgan: bir nuqtada biz
o'zgarishlar noto'g'ri ekanligini qaror mumkin va biz yana boshlash uchun xohish. Shunday
qilib, biz qaytarishimiz mumkin bo'lgan asl satrning nusxasini saqlashimiz kerak. Satr berilgan P, quyidagi algoritm ipni
hosil
qiladi PP va to'xtaydi. Markerlar: M9 algoritmini ishlab chiqish, ishlab chiqarish, ishlab chiqarish va sotish
M91: [prod. sxema]
ƒδβ →
δβƒ
O'zbekiston Respublikasi Markaziy saylov komissiyasining
navbatdagi majlisi bo'lib o'tdi.
M92: [prod. sxema]