Ii-bob. Markovning normal algoritmlari 1 Normal algoritm tushunchasi va uning bajarilish qoidasi

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