Ii-bob. Markovning normal algoritmlari

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).