Amaliy matematika va informatika kafedrasi

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.

3-misol. А={a,b} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. Bo’sh bo’lmagan P kirish so’zidagi birinchi simvolni o’chiruvchi , bo’sh kirish so’zini o’zgarishsiz qoldiruvchi algoritm tuzilsin.

Yechish: Algoritm kirish so’zidagi birinchi simvolni o’chirib, darhol ishini to’xtatishi kerak. Bunda quyidagi buyruqlardan foydalanish mumkin:

Ammo algoritmning bunday tuzilishi to’g’ri emas. Bunga algoritmni bbaba kirish so’ziga qo’llab amin bo’lish mumkin: bbaba a bbba. Markovning normal algoritmi masala shartida talab qilingan birinchi simvolni emas, balki birinchi “a” simvolini o’chirdi. Demak algoritm faqat birinchi simvoli “a” bo’lgan kirish so’zlaridagina to’g’ri ishlaydi. Agar Markovning normal algoritmidagi buyruqlar ning joyini o’zgartirsak, algoritm faqat birinchi simvoli “b” bo’lgan kirish so’zlarida to’g’ri ishlaydi. Bu muammoni hal etish uchun kirish so’zidagi birinchi simvolni qandaydir usul bilan belgilab olish usulidan foydalaniladi. Masalan, belgilanuvchi simvol oldidan “*” simvoli joylashtiriladi. Buning uchun quyidagi formuladan foydalanish mumkin: → * . Endi Markovning normal algoritmi quyidagi ko’rinishni oladi:

Ushbu algoritmning yuqorida keltirilgan bbaba kirish so’zi ustida ishlashini ko’raylik: