Ii-bob. Markovning normal algoritmlari

Birоr аlfаvitdа bеrilgаn funksiyaning kiymаtini hisоblоvchi аlgоritm fаqаt vа fаqаt funksiya nоrmаl hisоblаnuvchi bo’lsа, mаvjuddir.

10. 
    misol. А={a,b} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin. Bo’sh bo’lmagan P so’zning birinchi simvolini uning oxiriga o’tkazuvchi, bosh kirish so’zini o’zgartirishsiz qoldiruvchi algoritm tuzilsin. Masalan, bbaba → babab
    

Yechish: Ushbu masalani hal etish uchun quyidagi amallarni bajarish kerak:

• 
  P so’zning birinchi simvolini “*” simoli bilan belgilash.
  
• 
  Belgilangan simvolni * bilan birga yangi simolga almashtirish.
  
• 
  Yangi “A” yoki “B” simvolni P so’zning oxiriga o’tkazish.
  
• 
  “A” yoki “B” simvollarni asl nusxalari bilan almashtirish va algoritmni to’xtatish.
  

Ushbu amallarni bagaruvchi normal algoritm quyidagi ko’rinishga ega:

Bu yerda (1) va (2) formulalar kirish so’zining birinchi simvolini (* bilan birga) “A” yoki “B” simvollarga almashtiradi. (3) –(6) formulalar “A” va “B” simvollarni so’z oxiriga o’tkazadi. (7) va (8) formulalar “A” va “B” simvollar kirish so’zi oxiriga yetgandan keyin qo’llaniladi va ushbi simvollarni asl nusxalariga almashtiradi. (9) formula bo’sh kirish so’zi uchun ishlatiladi, (10) formula kirish so’zi birinchi simvoli oldiga “*” belgisini joylashtiradi. Ushbu algoritmni baba kirish so’zi uchun tekshirib ko’ramiz:

11. 
    misol. А={a,b} kirish so’zi alfaviti va Р kirish so’zi berilgan bo’lsin.P kirish so’zini ikkilantiruvchi algoritm tuzilsin. Masalan, abb → abbabb.
    

Yechish: Ushbu masalani hal etishda quyidagi amallar bajariladi:

• 
  P so’zning oxiriga “=” belgisini joylashtirish.
  
• 
  P so’zga kiruvchi barcha simvollar navbat bilan ko’rib chiqilib, ulardan “=” belgisining o’ng tomoniga nusxa ko’chirish.
  
• 
  “=” simvolini o’chirib, algoritmni to’xtatish.
  

Biror simvolni so’z oxiriga yozishni qanday bajarishni yuqoridagi misollarda ko’rib o’tdik: so’zning chap tomoniga “*” simvolini yozib, u so’zning o’ng tomoniga ko’chirib o’tkaziladi va “=” belgisi bilan almashtiriladi: