1-lektsiya. Qatnaslar. Binar qatnaslar

7-lektsiya. Sheshiliwshi ha`m sanaliwshi ko’plikler 

 Tayanısh tu’sinikler: Predikattın’  xarakteristikalıq   funktsiyası. Rekursiv  

h’a’m  rekursiv  sanalawshı  ko’plikler.Funktsiyanın’  grafigi,anıqlanıw  dawamı  

tu’sinikleri. 

Biz  lektsiyada  natural  sanlar  ko’liginin’   u’les  ko’pligin  qaraymız.Meyli 

A<=N 

Anıqlama:20.1              1  eger x

∈A 

                      X

A

(x)=  0 eger x

∈A 

Funktsiyası  A-ko’pliginin’  xarakteristikalıq  funktsiyası  delinedi. 

Anıqlama:20.2   Xarakterestikalıq  funktsiyası        ulıwma  rekursiv bolg’an 

ko’plik rekursiv ko’plik delinedi. 

Mısalı. A=

∅.A=N , A=2N - rekursiv  ko’plikler 

Teorema:20.3    EGER    A    h’a’m  V  lar  rekursiv  ko’plikler  bolsa, AUV 

,A

∩V lar h’a’m  rekursiv  ko’plik  boladı.  

Da’liylew: X

A

(X) h’a’m X

V

(X) lar  sa’ykes  h’a’m  V lardın’  xarakteristikalıq  

funktsiyaları  bolsa   

            X

AUV

(X)=S

g

(X

A

(X)+X

V

(X)  h’a’m 

            X

A

∩V

(X)= S

g

(X

A

(X)

⋅X

V

(X) lar  sa’ykes  A

∪V, h’a’m A∩V lar  ushın  

xarakteristikalıq  funktsiyalar boladı.  bular  ulıwma  rekursiv.  

Anıqlama:20.4  bos  yamasa  bazı bir  ulıwma  rekursiv  funktsiyalardı  

ma’selelerinen  ibarat bolg’an ko’plik   rekursiv  sanalıwshı  ko’plik  delinedi. 

  MISALI:  

ƒ(X)=2x+1, ƒ(x)=3x+2  ƒ(x)=x 

 

30

Teorema:20.5 Eger A-rekursiv  ko’plik  bolsa  ol  rekursiv  sanalıwshı  ko’plik  

boladı. 

Da’lillew  sxeması  u’sh  jag’day  qaraladı  

A)  A=0  , B)A=

A

0

, ..  .,A

K

 - shekli 

B)  A-sheksiz 

Birinshi  jag’day tu’sinikli, ekinshi  jag’dayda 

        A

X

  eger  X<=K 

ƒ(X)= A

K

  eger X>K 

sanawshı dizyunktsiya boladı. U’shinshi  jag’dayda X

A

(X)  xarakteristikalıq 

funktsiya  bolsa   

    

ƒ(0)=µ

U

[X(U)=1]  

   

ƒ(X+1)=µ

U

[X

A

(U)=1 

&U&ƒ(X)] 

 sanawshı  dizyunktsiya  boladı. 

Anıqlama:20.6 

 

ƒ(X

1, ..   .. 

,X

N

)= 

1 R(X

1

, ..   ,X

N

)=ras  bolsa 

0R(X

1

, ..   ,X

N

)=jalg’an  bolsa 

funktsiyası  natural  sanlar  ko’pliginde  anıqlang’an 1 R(X

1

, . . . ,X

N

)  

predikatının’ xarakterestikalıq  funktsiyası  delineli. 

  Teorema:20.7  A-ko’pligi  rekursiv  sanalıwshı  bolıwı  ushın, ol  

⊃XR(X,U)  

ko’rinisine  iye  bolg’an  predikattın’  raslıq  ma’nislerinen  ibarat  bolıwı  za’ru’rli  

h’a’m  jetkilikli. 

Xarakterestikalıq  funktsiyası  ulıwma  rekursiv  (preliktiv  rekursiv)  predikat  

delinedi. 

Saldar:20.I  A-rekursiv  ko’plik  bolıwı    ushın  ol  qandayda  bir  ulıwma  

rekursiv  predikattın’  raslıq  ma’nislerinen  turıwı  za’ru’rli  h’a’m  jetkilikli. 

     Sorawlar  h’a’m  shınıg’ıwlar 

1..2N+1 ko’pligi  rekursi  sanalıwshı  bolama

? 

2. To’mendegi  ko’pliklerdi  rekursiv  sanap  shıg’ıwshı  diziktsiyalardı  jazın’. 

A)  2N,  B) P=

2,3,4,  .. ,..  V) E=2

0

,2

1

,2

2

, . . .

 

 

31

8- lekiya. Esaplaniwshi funktsiyalar. Primitiv ha`m uliwma primitiv 

funktsiyalar. 

Tayanish tu`sinikler. Arifmetik funktsiya. Hisoblanuvchi funktsiya. Boshlang`ich 

funktsiyalar. Funktsiyalar superpozitsiyasi. Primitiv rekursiya sxemasi. Minimallash 

operatsiyasi (µ- operator). Primitiv rekursiv funktsiya.  

1 - t a ` r i f .  Agar biror funktsiyaning aniqlanish soxasi ham, kiymatlar soxasi xam 

natural sonlar to`plamining qism to`plamlari bo`lsa, u holda bunday funktsiya 

arifmetik (sonli) funktsiya deb ataladi. Natural sonlar to`plamida berilgan har kanday 

munosabatlar arifmetik munosabat deyiladi. 

Masalan, natural sonlar to`plamida f(x,u)=x*u (ko`paytma) — ikki argumentli 

arifmetik funktsiyadir, x+u

funktsiya va arifmetik munosabat tushunchalari intuitiv tushunchalardir va hech 

qanday formal sistema bilan bog`langan emas. 

Arifmetik (sonli) funktsiyaning qiymatini hisoblov-chi algoritm mavjudligini 

aniklash algoritmik muammo-lardan biridir. 

2 - t a ` r i f .   Agar  g=f(x

1

, x

2

, ..., x

n

) funktsiyaning qiymatini hisoblovchi algoritm 

mavjud bo`lsa, u effektiv (samarali) hisoblanuvchi funktsiya deb ataladi. 

Bu ta`rifda algoritm tushunchasi intuitiv ma`noda tushunilganligi sababli, 

effektiv hisoblanuvchi funktsiya tushunchasi ham intuitiv tushuncha bo`ladi. 

Ammo algoritm tushunchasidan effektiv hisoblanuvchi funktsiya tushunchasiga 

o`tishning o`ziga xos ijobiy tomoni bor. Masalan, algoritm tushunchasiga qo`yilgan 

hamma ta-lablar (xarakterli xususiyatlari sifatida) rekursiv (qaytarish) funktsiyalar 

majmuasi deb ataladigan hamma hisoblanuvchi funktsiyalar majmuasi uchun 

bajariladi. 

Gyodel birinchi bo`lib biror formal sistemada aniklangan hamma sonli 

funktsiyalar sinfini rekursiv funktsiyalar sinfi sifatida ifodaladi. 1936 yilda Chyorch 

ham boshqa asoslarga tayanib rekursiv funktsiyalar sinfini tasvirla-gan edi. Bu erda 

hisoblanuvchi funktsiyalar sinfi quyidagi ravishda tuziladi. 

 

32

3-ta`rif. Kuyidagi sonli funktsiyalar boshlantch (oddiy, bazis) funktsiyalar 

deyiladi: 

1)  nol` funktsiya (bekor qilish operatori): 0(x) = 0 har bir x uchun; 

2) birni qo`shish (siljish operatori): λ(x) = x + 1 har bir x uchun; 

3) proektsiyalash funktsiyasi (proektsiyalash operatori): I

n

m

(X

1

  x

2

, ..., x

n

)=x

m

 

hamma x

1

 x

2

, ..., x

n

 lar uchun (n= 1, 2, ...; m = 1, 2, ..., n). 

Ravshanki, uchala boshlang`ich funktsiya hamma joyda aniqlangan va intuitiv 

hisoblanuvchi funktsiyalardir. 

Izoh. Argumentlarining barcha qiymatlarida aniq-langan funktsiyani hamma 

joyda anitslangan funktsiya deb ataymiz. 

Quyidagi uchta qoida vositasi bilan mavjud funktsiya-lardan yangi funktsiyalar 

hosil qilinadi. 

Primitiv (o`ta sodda) rekursiya sxemasi.  φ(x

2

, x

3

, ..., x

n

) va  ψ(x

1

, x

2

, ..., x

n

, x

p+1

)    

(n > 1) funktsiyalar berilgan bo`lsin. Quyidagi tengliklarni qanoatlantiruvchi yangi f 

funktsiyani ko`ramiz: 

f (0, x

2

, x

3

, ..., x

n

 ) = φ(x

2

, x

3

, ..., x

n

), 

f (y+1, x

2

, x

3

, ..., x

n

) = ψ (y,f(y, x

2

, x

3

 ..., x

n

), x

2

, ..., x

n

),       (1) 

bu erda f funktsiya n-1 argumentga, ψ funktsiya n+1 argumenta va f funktsiya n 

argumentga bog`liq funktsiya. 

5- ta`r i f . Agar f(x

1

,x

2

, ..., x

n

) funktsiya φ va ψ funktsiyalardan (1) munosabat 

orkali hosil qilinsa, u holda f funktsiya φ va ψ funktsiyalardan primitiv               (o`ta 

sodda) rekursiya sxemasi orkali hosil qilingan deyiladi. 

Agar  φ va ψ funktsiyalar intuitiv hisoblanuvchi funktsiyalar bo`lsa, u holda f 

ham intuitiv hisoblanuvchi funktsiya bo`ladi. Haqiqatan ham, x

1

,x

2

, ..., x

n

 

argumentlarning qiymatlar majmuasi a

1

,a

2

, ..., a

n

 bo`lsin. U holda ketma-ket 

quyidagilarni topamiz: 

f(0, a

2

, a

3

 ..., a

N

)

 

=

 

φ (a

 

2

,

 

a

3

, ..., a

n

) = b

0

, 

f (1, a

2

, a

3

, ..., a

n

) = ψ (0, b

0

, a

2

, a

3

, ..., a) = b

1

 

f

 2

(2, a

2

, a

3

, ..., a

n

) = ψ (1, b

r

 a

2

, a

3

, ..., a

n

) = b

2

  va hokazo. 

 

33

Ravshanki, agar φ va ψ funktsiyalar argumentlarning barcha qiymatlarida 

aniklangan bo`lsa, u holda f funktsiya ham argumentlarning barcha kiymatlarida 

aniklangan bo`ladi. 

 

9-lektsiya. Tyuring mashinaları 

Tayanısh tu’sinikler: Sırtqı h’a’m ishki alfavit, programma, mashina so’zi, 

esaplawshı funktsiya. 

Tyuring mashinası qıyalıy mashina bolıp, ol to’mendegi u’sh na’rse menen tolıq 

anıqlanadı. 

a) Sırtqı alfavit A= 

{a

0

,a

1

,...,a

n 

} (a

0

 =0 a

8

=1) 

b) İshki alfavit Q={q

0

,q

q

,…,q

m

} 

v) Programma. Bul T(i,j) (i=1,…,m; j=1,…,n) 

tu’rindegi an’latpalar bolıp olardın’ h’a’rbiri to’mendegi ko’rinislerdin’ birewine 

ten’ boladı. 

q

i

a

j

 

→q

k

q

l   

,

   

q

i

a

j

 

→q

k

q

l 

R, q

i

a

j

 

→q

k

q

l 

L. 0

≤k≤m 0≤l≤n A,V so’zleri bosta bolıwı 

mu’mkin. a

8

, a

8

..., a

8

= a

8

x

 dep belgilep alamız 

Meyli T mashinası h’a’m M=Aq

i

a

j 

B mashina so’zi berilsin. (0

≤i ≤m) M'

t

 M nen 

to’mendegi qa’de boyınsha alıng’an so’zdi belgileymiz. 

(1) i=0 M'

t

 =M 

(2) Eger i>0 bolsa  

Eger T(i,j), q

i

a

i 

→q

k

a

l 

M'

T 

=A

qk

a

i

B 

B) Eger T(i,j), q

i

a

j

=q

k

a

l

R tu’rinde bolsa,  

B

1

)  Eger V bos emes bolsa, onda M'

T

=Aa

l

q

k

B 

B

2

) Eger V=

∅ bolsa, M'

T

=Aa

l

q

k

a

0

 

V) Eger T(i,j), q

i

a

j

=q

k

a

l

L ko’rinisinde bolsa, onda 

V

1

) Eger A=A

1

a

s 

(A

1

 h’a’m a

s 

ushın) bolsa, onda M'

T

=Aq

k

a

s

a

l

B, 

B

2

) Eger A>

∅ bolsa, onda M'

T

=q

k

a

0

a

l

B, M

(0)

T

=M , M

(n+1)

T

=(M

n

T

)' dep belgilep 

alamız. 

Eger M

(n)

T

=M

1 

bolsa T mashinası M so’zin M

1 

so’zine qayta isleydi dep aytamız. 

Eger T mashinası M di M

1 

ge qayta islese h’a’m anıqlamadag’ı (V

2

) qollanbasa 

 

34

M

≡M

1

 dep jazamız. Al egerde T mashinası M di M

1 

ge qayta islep anıqlamadag’ı (B

2

) 

h’a’m (V

2

) punktlerdi qollanbasa M

≡>M

1

 dep jazıladı. 

T mashinası n-orınlı 

δ

f

⊆N

n

, 

ρ

f

 

⊆N bolg’an f-dara funktsiyasın esaplaydı delinedi 

egerde to’mendegi sha’rtler orınlang’an bolsa: 

a) Eger

1

,...,x

n

>

∈δ

f

 bolsa mashina toqtaydı yag’nıy mashina q

1

01

x1

0…1

xn

0 

so’zin bazıbir A1

0

B so’zine qayta isleydi h’a’m Aq

0

B so’zi 1 simvolının’ f(x

1

,...,x

n

) 

ret o’zinde tutadı. 

b) Eger

1

,...,x

n

>

∉ δ

f

  bolsa mashina o’z jumısın  

M= q

1

01

x1

0…1

xn

0 so’zinen baslap sheksiz dawam etedi, yag’nıy h’esh qanday 

n-ushın 1

0

 M

(n)

T

 ge kirmeydi. 

Eger f-funktsiyasın esaplaytug’ın Tyuring mashinası bar bolsa f- funktsiyası 

esaplanatug’ın funktsiya delinedi. 

Meyli T

1

,T

2

,T

3

 ler A= {x

q

,...,x

n

} Q

1

={q

0

,q

1

,…,q

r

}, Q

2

={q

0

,q

1

,…,q

s

} h’a’m 

Q

3

={q

0

,q

1

,…,q

i

} bolg’an u’sh mashina bolsın. Bul mashinalardın’ programmaları 

sa’ykes tu’rde P

1,

P

2   

h’a’m P

3 

bolsın. T

1

 h’a’m T

2

 mashinalarının’ kompozitsiyası dep 

programması  S

10

14+1

P

1 

 h’a’m S

11…1s

14+s

P

2

 bolg’an T mashinasına aytıladı. (Bunda 

S

1j

18

P -ko’pligi P komandadag’ı barlıq 1

j  

lardı

           

1

8

 larg’a almastırıwdan alıng’an 

komandalar ko’pligi.) 

T

1,

T

2,

T

3

 mashinalarının’ (1

8  

,

 

1

j 

) boyınsha ) tarmaqlanıwı dep programması P

1

 

den T

1

(i,k) h’a’m T

1

(j,k) lardı shıg’arıp tastalg’an programmag’a ten’ bolatug’ın T 

mashinasına aytıladı. Ol programmanı P' desek  

P=P'

1 

∪ S

11…1s

1814+1...14+s-1

P

2

 

∪ S

11...1s

1j+14+s...14+s+5-2

P

3 

boladı. 

Shınıg’ıwlar. 

1. To’mendegi komandalar menen berilgen Tyuring mashinası qanday 

funktsiyanı esaplaydı. 

Q

1

0

→1

2

0k             1

2

0

→1

0

1 

1

1

1

→1

0

1                1

2

1

→1

2 

1k 

2 Funktsiyalardı esaplaytug’ın Tyuring mashinasın du’zin’. 

a) x+u   b) x\2   v) sg(x) 

 

35

 

10- lektsiya. T`yuring mashinasinda algoritmlerdi realizatsiyalaw. 

Tayanish tu`sinikler: Algoritmlarni realizatsiya etish. O`nlik sistemada p dan n + 1 ga 

o`tish algoritmini realizatsiya kilish. Natural sonlarni qo`shish algoritmini realizatsiya qilish. 

evklid algoritmini realizatsiya qilish. 

 

Ayrim oddiy arifmetik algoritmlarni realizatsiya qiladigan (amalga oshiradigan) 

T`yuring mashinasini qanday yasashni bir qator misollarda ko`rsatamiz. 

1-  m i s o l. T`yuring  manshnasida o`nlik sistemada n dan n + 1  ga o`tish 

algoritmini realizatsiya qilish. 

e ch i m . O`nlik sistemada n sonning yozuvi berilgan bo`lsin va n + 1 sonning 

o`nlik sistemadagi yozuvini ko`rsatish talab etilsin, ya`ni f(n) = n+1 funktsiyani 

hisoblash talab etilsin. 

Ravshanki, mashinaning tashki alfavita 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 raqamlaridan va 

bo`sh katakcha a

0

 dan iborat bo`lishi kerak. Lentaga o`nlik sistemada n sonni 

yozamiz. Bu erda katorasiga bush joysiz har bir katakchaga bitta raqam yoziladi. 

Qo`yilgan masalani echish uchun ishning birinchi taktida mashina n sonning oxirgi 

raqamini o`chirib, uni bir birlik katta songa almashtirib va agar oxirgi rakam 9 

sonidan kichik bo`lsa, u holda to`xtash holatiga utishi kerak. Agar n sonning oxirgi 

raqami 9 bo`lsa, u holda mashina 9 raqamini o`chirib, bo`sh qolgan katakchaga 0 

raqamini yozib, o`sha holatda qolgan holda chapga yuqoriroq razryadli qo`shnisiga 

surilishi kerak. Bu erda ishning ikkinchi taktida mashina yuqoriroq razryadli raqamga 

1 sonini qo`shishi kerak. 

Tabiiyki, chapga surilish paytida yuqoriroq razryadli raqam bo`lmasa, u holda 

mashinaning boshqaruvchi kallagi bo`sh katakchaga chikdshi mumkin. Bu holatda 

bo`sh katakchaga mashina 1 raqamini yozadi. 

Aytilganlardan shu narsa kelib chiqadiki, f(n) = n + 1 funktsiyani hisoblash 

algoritmini realizatsiya etish paytida mashina bor yo`g`i q

1

 va q

0

 holatlarda bo`ladi. 

 

36

Shunday qilib, o`nlik sistemada n dan n + 1 ga o`tish algoritmini realizatsiya 

etadigan T`yuring mashinasi quyidagi ko`rinishda bo`ladi: 

 

 

a

0

 

0 

1 

2 

3 

4 

5 

6 

7 

8 

9 

q

1

  1hq

0

  1 hq

0

2 hq

0

  3hq

0

  4 hq

0

5 hq

0

6 hq

0

7 hq

0

8 hq

0

  9 hq

0

  0 hq

0

Quyida n = 183 va n = 399 sonlari uchun moc ravishda ularning 

konfiguratsiyalari keltirilgan: 

a

0

183 a

1

 

a

0

 399 a

0

 

     q

1

 

q

1

 

a

0

184 a

0                                                         

a

0

 390 a

0 

     q

1

 

       q

1

  

                                                      a

0

 300 a

0

 

                                                            q

1 

                                                       a

0

 400 a

0

 

                                                            q

1 

 

37

11-lektsiya. Markovtin` normal algoritmleri. 

Tayanish tu`sinikler: Alfavit. Simvollar. Harflar. So`z. Bo`sh so`z. Algoritm. Algoritm 

ta`rifi. Alfavit ustidagi algoritm. Alfavitdagi algoritm. Tatbiq etiladigan algoritm. Tatbiq 

etil-maydigan algoritm. Urniga qo`yish usuli. Algoritm sxe-masi. Normal algoritm 

yoki Markov algoritmi. Misollar. 

1 - t a ` r i f .   Bo`sh bo`lmagan chekli simvollar to`plami alfavit va alfavitdagi 

simvollar harflar deb ataladi. 

2-ta`rif. A alfavitdagi harflarning harqanday chekli ketma-ketligi shu 

to`plamdagi so`z deb ataladi. Harflarning bo`sh ketma-ketligi bo`sh so`z deb ataladi 

va uni ^ simvoli bilan belgilanadi. 

Agar S

j1

 S

j2

 ...S

jn

   so`zni R bilan va S

r1

 S

n

...S

r

   so`zni Q 

bilan belgilasak, u holda S

h

  S

;

 ... S, S

r1

  S

r2

... S

rm

 so`z P va Q so`zlarning 

birlashmasi PQ ni bildiradi. Xususiy holda, R ^ - ^ R = R v a                            (P

1

R

2

)P

z

 

= P

1

(R

2

R

3

). 

Agar V

⊂

A bo`lsa, u holda A alfavit V alfavitning kengayishi (kengaytirilgani) 

deb aytiladi. Ravshanki, bu holda V ning har bir so`zi o`z navbatida A alfavitining 

ham so`zi bo`ladi. 

A alfavitdagi hamma so`zlarning to`plami D, S esa D to`plamning biror qism 

to`plami bo`lsin, ya`ni S 

⊂

D. 

3 - t a ` r i f .  Aniqlanish sohasi S va qiymatlar sohasi D bo`lgan effektiv 

hisoblanuvchi funktsiya A alfavitdagi algoritm (algorifm) deb ataladi. 

4- t a ` r i f . Agar A alfavitdagi biror R so`z U algoritm-ning aniqlanish sohasiga 

tegishli bo`lsa, u holda U algoritm R so`zga tatbiq etiladigan deb ataladi. 

5-ta`rif. Agar A

⊂

V  bo`lsa, u holda V alfavitdagi har bir algoritm A alfavit 

ustidagi algoritm deb ataladi. 

A alfavitdagi normal algoritm tushunchasi bilan A alfavit ustidagi normal 

algoritm tushunchasi o`rtasidagi farq juda ham muhimdir. A alfavitdagi har qanday 

normal algoritm faqat A ning harflaridan foydalanadi. A alfavit ustidagi normal 

algoritm esa A ga kirmagan boshqa qo`shimcha harflardan ham foydalanishi 

 

38

mumkin. Shunday qilib, A dagi har qanday normal algoritm A ustidagi normal al-

goritm ham bo`ladi. Ammo A da shunday algoritmlar mavjudki, ular A ustida normal 

algoritm ekanligiga qara-masdan, A da normal algoritm bo`la olmaydi. 

Ko`p aniqlangan algoritmlarni birmuncha oddiyroq qadamlarga bo`lish mumkin. 

Shu maqsadda rus matematigi A.A. Markov 1950 yillarda algoritm tuzishning asosi 

(negizi) qilib, elementar operatsiya sifatida bir so`zni ikkinchi so`z o`rniga ko`yishni 

olgan. 

Agar R va Q lar A alfavitdagi so`zlar bo`lsa, u holda R → Q va R→·Q larni A 

alfavitdagi o`rniga ko`yish formulalari deb ataymiz. Bu erda → va · simvollari A 

alfavitning harflari emas hamda R va Q larning har biri so`z bo`lishi mumkin. R→ Q 

o`rniga qo`yish formulasi oddiy formula va R →· Q o`rniga qo`yish formulasi natijaviy 

(xulosaviy) formula deb ataladi. 

Berilgan R → Q va R→· Q o`rniga qo`yish formulalarining istalgan birini 

ifodalash uchun P →( ·) Q  umumiy ko`rinishdagi yozuvni ishlatamiz. 

Alfavitning quyidagi o`rniga qo`yish formulalarining chekli ro`yxati 

P

1

→ (·)Q

1

 

P

2

 → (·)Q

2

, 

………………….. 

P

r

 → (·)Q

r

, 

 

algoritm sxemasi deb ataladi va u A alfavitda quyidagi algoritmni yuzaga 

keltiradi: agar shunday W, V so`zlar (bo`sh so`z bo`lishlari mumkin) topilib,  

Q = WTV bo`lsa, u holda T so`z Q so`zning tarkibiga kiradi deb kelishib olamiz. 

Endi A alfavitda R so`z berilgan bo`lsin. Bu erda ikki hol bo`lishi mumkin: 

1. R

1

, R

2

, ..., R

r

 so`zlarning birortasi ham R so`zning tarkibiga kirmaydi. Bu 

tasdiqni qisqa ravishda U: R

⊃

 shaklida yozamiz. 

 

39

2. P

1

  R

2

, ..., R

k

 so`zlarning orasida R so`zning tarkibiga kiruvchilari topiladi. 

Endi 1 ≤  m≤r munosabatni qanoatlantiruvchi eng kichik butun son m va P

m

 so`z P 

ning tarkibiga kiruvchi so`z bo`lsin. 

R so`zning tarkibiga eng chapdan kirgan R

t

 so`zni Q

m 

bilan almashtirishdan 

hosil bo`ladigan so`zni R deylik. R va R orasidagi aytilgan munosabatni: 

a) agar 

R→(·)Q

m

 o`rniga qo`yish formulasi oddiy formula bo`lsa, 

U : P ├ R                                               (1) 

shaklida va; 

b) agar 

R→(·)Q

m

  o`rniga qo`yish formulasi natijaviy formula bo`lsa, 

U :  ├ R                                           (2) 

shaklida yozamiz. 

(1) holda U algoritm R so`zni R so`zga oddiy o`tkazadi deyiladi va (2) holda U 

algoritm R so`zni R so`zga natijaviy o`tkazadi deb aytiladi. 

U: R├  R simvolik yozuv A alfavitda shunday R

0

, R

1

 ..., R

k 

so`zlar ketma-ketligi 

mavjudki, P=R

0

,

 

R = R

k

, j = 0, 1, ..., k-2 lar uchun U:R

j

├ R

j + 1

 va yoki U:R

k-1

├ R

k

, 

(oxirgi holda U: P│=R o`rniga U: P│= R yoziladi) ekanligini bildiradi. 

Yoki U: P│=R, yoki U: P│=R va U:R

⊃

) bo`lganda va faqat shundagina U(P) = 

R deb qabul qilamiz. 

Yuqoridagi kabi aniqlangan algoritm normal algoritm yoki Markov algoritmi 

deb ataladi. 

U algoritmning amal qilishini quyidagicha ifodalash mumkin. A alfavitda R so`z 

berilgan bo`lsin. U algoritm sxemasida R

m

 so`z R ning tarkibiga kiruvchi birinchi R

m

 →(· 

)Q

m 

o`rniga qo`yish formulasini topamiz. R so`zning tarkibiga eng chapdan kirgan R

m

 

so`z o`rniga Q

m

 formulani qo`yamiz. R

1

 shunday o`rniga qo`yishning natijasi bo`lsin. 

Agar R

m

 →(· )Q

m 

o`rniga qo`yish formulasi natijaviy bo`lsa, u holda algoritmning ishi 

tugaydi va uning qiymati R

1

 bo`ladi. Agar R

m

  →(· )Q

m  

o`rniga qo`yish formulasi 

oddiy bo`lsa, u holda R

1

 ga R ga nisbatan ishlatilgan protsedurani bajaramiz va 

hokazo. Agar oxirgi bosqichda U:R

i

⊃

 munosabatni qanoatlantiruvchi (ya`ni, P

1

 R

2

, 

..., R

g

 so`zlarning birortasi R

i

 tarkibiga kirmaydi) R

i

 so`z hosil bo`lsa, u holda 

algoritmning ishi tugaydi va R

i

 uning qiymati bo`ladi. 

 

40

Agar ifodalangan jarayon oxirgi bosqichda tamom bo`lmasa, u holda U algoritm 

R so`zga tatbiq etilmaydi deb aytiladi. 

1-misol . {b, s} A alfavit bo`lsin. Quyidagi algoritm sxemasini ko`ramiz: 







→

∧

⋅

→

c

c

b

 

Bu sxema bilan berilgan U normal algoritm A alfavitdagi tarkibiga kamida bitta 

b harfi kirgan har qanday R so`zni shunday so`zga o`zgartiradiki, bu so`z R so`zdan 

uning tarkibiga eng chapdan kirgan b so`zni o`chirish natijasida hosil bo`ladi. 

Haqiqatan ham, P so`z tarkibiga eng chapdan kirgan b so`zdan chaproqda turgan 

har qanday s harfni s→ s oddiy o`rniga qo`yish formulasi yana s harfiga o`tkazadi va 

eng chapdagi b harfini b→·^  natijaviy o`rniga qo`yish formulasi ^  natijaviy bo`sh 

so`zga o`zgartiradi. 

Masalan, agar R = ssbbs bo`lsa, u holda R →· Q, bu erda Q = ssbs. U algoritm 

bo`sh so`zni o`z-o`ziga o`zgartiradi. 

U algoritm b harfi kirmagan bo`sh bo`lmagan so`zlarga tatbiq etilmaydi. 

Haqiqatan ham, agar R so`z faqat s harflardan iborat bo`lsa, u holda s→ s oddiy 

o`rniga qo`yish formulasi uni yana o`ziga aylantiradi. U holda hamma vaqt R→ R 

bo`ladi va biz natijaviy o`rniga qo`yish formulasiga kela olmaymiz, ya`ni jarayon 

cheksiz davom etadi.