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

:
abb → *abb → a*bb → ab*b → abb* → abb=. 

---

Shuningdek, so’zdagi simvollarni so’z oxiriga ko’chirib o’tkazish ham ko’rib 
o’tildi, ammo ushbu misolda simvollar nusxalanishi kerak bo’lganligi uchun ular 
eski joyidan o’chirilmaydi. Buning uchu nusxasi olinishi kerak bo’lgan simvol 
ketidan yangi simvol qo’shiladi (masalan, “a” simvol “aA” qism so’z bilan 
almashtiriladi), so’ngra bu simvol so’zdagi nabatdagi simvollar bilan ketma-ket 
o’rin almashib, so’z oxiriga ko’chiriladi. Simol “=” belgisining o’ng tomoniga 
o’tgach, “a” simoliga aylantiriladi:
abb= → aAbb= → abAb= → abbA= → 
abb=A → abb=a.
Xuddi shu tarzda barcha “b” simollarining nusxasi olinadi. Bu 
takrorlanuvchi jarayonda qaysi simvol navbatda nusxalanish kerak?- degan savol 
tug’iladi, chunki nusxasi olingan simollar hech qanday usul bilan belgilanmaydi va 
nusxasi olinmagan simvollardan farq qilmaydi. Buning uchun navbatda nusxasi 
olinishi kerak bo’lgan simvolni “#” simoli bilan belgilash usuludan foydalanamiz
: 
#abb= → a#Abb= → a#bAb= → a#bbA= → a#bb=A → a#bb=a
. Nusxasi 
olinayotgan simvol “=” belgisining o’ng tomonida paydo bo’lishi bilan “#” belgisi 
navbatdagi simol oldiga o’tkaziladi:
 a#bb=a → ab#Bb=a → ab#bB=a → ab#b=Ba → ab#b=aB → ab#b=ab → 
→ abb#B=ab → abb#=Bab → abb#=aBb → abb#=abB → abb#=abb 
jarayon “#” belgisi o’zining o’ng tomonida “=” belgisini uchratgunga qadar daom 
etadi. Ushbu hol yuz berishi bilan “=” va “#” belgilari o’chiraladi hamda algoritm 
to’xtatiladi. Yuqoridagi amallarni bajaruvchi Markovning normal algoritmining 
ko’rinishi quyidagicha: 

---

Ushbu algoritmni bo’sh so’z va abb kirish so’zlari uchun sinab ko’ramiz:
→ #* → #= a (bo’sh so’z uchun).