Программа тузишга мисоллар Режа: Тьюринг машинасида (ТМ) автоматни силжитиш, белгиларни алмаштириш

7-мисол. Сўзни ёйиш.
A={a,b,c}. Р сўзидаги биринчи учраган с белгисидан сўнг а белгисини қўйинг, агар шундай белги Р да учраса.
Ечилиши. Кириш сўзини чапдан ўнгга томон бўш катакгача ёки биринчи учраган с белгисигача кўриб чиқамиз. Биринчи ҳолда с белгиси Р га кирмайди, шунинг учун ҳеч нарса қилинмайди. Иккинчи ҳолда қўйиладиган а белгиси учун жой ажратиш керак бўлади, бунинг учун Р сўзининг бошини битта белги чапга силжитамиз (биринчи белгидан бошлаб токи с белгисигача). Шунда ўнгдан чапга томон с белгисидан сўз бошигача силжиш амалга оширилади. Бундай чапга томон циклик силжиш 5-мисолдаги ўнгга силжиш каби амалга оширилганлиги боис, уни тушунтириб ўтирмаймиз ва бирданига ТМ учун программани келтирамиз:

	a	b	c	Λ	Изоҳ
q1	,R,	,R,	a,L,q4	,L,!	Ўнгга с гача, с ўрнига а ни, с ни чапга ўтказиш
q2	,L,	a,L,q3	a,L,q4	a, ,!	ўнгдан а ни ўтказиш
q3	b,L,q2	,L,	b,L,q4	b, ,!	ўнгдан b ни ўтказиш
q4	c,L,q2	c,L,q3	,L,	c, ,!	ўнгдан c ни ўтказиш

21-расм.
8-мисол. Сўзни янги жойда расмийлаштириш.
A={a,b,c}. Р сўзидаги учраган барча а белгиларини ўчиринг.
Ечилиши. Олдинги мисоллар шуни кўрсатадики, ТМда сўзга бирор белгиларни қўшиш ва уларни олиб ташлаш анча қийин реализация қилинар экан. Шу сабабли баъзан кириш сўзини сиқишга қараганда, чиқиш сўзини лентанинг бошқа бир бўш жойида расмийлаштириш осонроқдир. Бу масалани айнан мана шундай усулда ечишга ҳаракат қиламиз.
Айнан амалларни бажариш қуйидагича таклиф этилади:
1.Чиқиш сўзини кириш сўзининг ўнг томонидан бошлаб қурамиз. Бу сўзларни фарқлаш учун уларни бирор ёрдамчи белги билан ажратамиз, масалан, А алфавитдаги белгилардан фарқли бўлган = белгиси билан (1- қадамга қаранг). Лентада алфавитдаги белгилардан ташқари бошқа белгилар ҳам бўлиши мумкинлигини эслатиб ўтамиз.
2.Бундан сўнг кириш сўзининг бошига қайтилади (2- қадамга қаранг).

а

b

c

а

b

c

=

а

b

c

=

3


2

1

22-расм.

5

4
3.Бизнинг эндиги ишимиз-циклда кириш сўзидаги а белгисидан бошқа барча белгиларни = белгисидан ўнг томонга, чиқиш сўзи расмийлаштириладиган жойга ўтказинг. Бунинг учун кириш сўзининг биринчи белгиси таҳлил қилинади. Агар бу а бўлса, у ўчирилади ва кейинги белгига ўтилади (3-қадамга қаранг). Агар биринчи белги b ёки с бўлса, у ҳолда уни ўчириб, ўнг томонга шу белгини ёзиш жойи, биринчи бўш катакгача “югурамиз” (4-5 қадамларга қаранг).

b

c

c

=

6

c

=

b

23-расм.

8

7
Яна чап томондаги кириш сўзида биринчи бўлган белгига қайтамиз ва ўша амалларни қайтарамиз, аммо мана шу белгига нисбатан (6-9 қадамларга қаранг).

с

=

=

b

9

b

c

24-расм.

10
4.Қайтган пайтда чап томонда кириш сўзининг биринчи белгиси сифатида = белгисини кўрсак, бу цикл тугайди. Бу кириш сўзини тўлиқ кўриб чиққанлигимизнинг белгиси бўлиб, а дан бошқа барча белгиларни чиқиш сўзи сифатида ўтказганлигимизни билдиради. Бу белгини ўчириш керак, ўнгга чиқиш сўзининг остига силжишни ва тўхташ кераклигини билдиради (10-қадамга қаранг).

b

c

b

c

25-расм.
Ҳамма айтилганларни ҳисобга олиб ТМ учун программа тузамиз. Шуни ҳам таъкидлаш керакки, масалани ечиш жараёнида a, b ва с белгилари билан бир қаторда лентада = белгиси ҳам пайдо бўлади, шунинг учун жадвалда бу белги учун ҳам устун бўлиши керак.

	a	b	c	=	Λ
q1	,R,	,R,	,R,	х	=, ,q2	Ўнг томондан = белгисини ёзиш
q2	,L,	,L,	,L,	,L,	,R,q3	Чапга сўзнинг биринчи белгисига
q3	Λ,R,	Λ,R,q4	Λ,R,q5	Λ,R,!	x	Унинг таҳлили ва ўчириш, тармоқланиш
q4	,R,	,R,	,R,	,R,	b, ,q2	Ўнгдан b ни ёзиш, чапга қайтиш (циклга)
q5	,R,	,R,	,R,	,R,	c, ,q2	Ўнгдан с ни ёзиш, чапга қайтиш (циклга)

26-расм.
9-мисол. Лентада жойни фиксирлаш.

A={a,b}. P кириш сўзи билан унинг нусхаси орасига = белгисини қўйиб иккилантиринг. Масалан:

а

а

b

а

а

b

=

а

а

b

27-расм.
9. Масала (тасмада жойни фиксирлаш)

. сўз ва унинг нусҳаси орасига = белгисини қўйиб, уни иккилантиринг.
Масалан,

a

a

b

a

a

b

=

a

a

b

28-расм.
Ечим

Бу масала қуйидагича ечилади: кирувчи сўзнинг охирига = белгисини қўямиз, кейин сўзнинг бошига қайтамиз ва циклда унинг барча символларини (а ни ҳам) бўш катакларга кўчирамиз:

a

a

b

a

a

b

=

a

a

b

=

a

a

b

=

a

1

2

29-расм.
Кирувчи сўзнинг кўчирилаётган белгилари ўчирилмайди ва бу қуйидаги муаммога олиб келади. Ўнг тарафда кейинги белгининг нусхасини ёзиб биз киритилувчи сўзнинг шу белги турган ўрнига қайтишимиз керак ва ундан кейинги турган ўнгдаги белгидан нусха олишмиз керак. Лекин киритилувчи сўзнинг қайси белгисига қайтиш кераклигини қандай биламиз? Масалан, бизнинг масалада биринчи а белгини кўчиргандан сўнг киритилувчи сўзнинг айнан биринчи белгисига қайтишни кераклигини қаердан биламиз? Аввалги масалада биз ҳар доим қолган белгилардан биринчисига қайтар этдик, энди эса биз ҳамма белгиларни қолдиряпмиз, шунинг учун қайси белгилардан нусҳа олганимиз, қайсиларидан эса олмаганимиз тушунарсиз. Яна шуни таъкидлаб ўтамизки, ТМ (Тьюринг машинаси) да тасма ячейкалари ҳеч қандай рақамланмайди, шунингдек ТМда қанча белгидан нусҳа олганлигимизни кўрсатувчи ҳеч қандай ҳисоблагичлар ҳам йўқ.

Биз дуч келган муаммо умуман олганда қуйидагича: тасмада биз бўлган вазиятни ва кейин келишимиз керак бўлган вазиятни (позиция) қандай белгилашимиз мумкин? Одатда бу масала қуйидагича ечилади. Биз шу позицияга биринчи мартта келганимизда унда турган белгини унинг ўхшаши (янги ёрдамчи белги) билан алмаштирамиз, бунда турли хил белгилар турли хил ўхшашлар билан алмаштирилади, масалан, белги га ва белги га. Бундан кейин биз тасманинг бошқа жойларида қандайдир амаллар бажарамиз. Кейинчалик бизнинг позицияга қайтиш учун тасмада ёки белгилар жойлашган катакни топиш керак. Агар кейинчалик бизга бу позиция керак бўлмаса, шу катакка аввалги белгини тиклашимиз мумкин (айнан аввалги белгини тиклаш учун бизга турли белгиларни турли ўхшашлар билан алмаштириш керак эди).
Қуйидаги амалларни бажариб бу усулдан қўйилган масалани ечишда фойдаланамиз:
1. Аввал айтилгандек, киритилувчи сўздан кейин = белгисини қўямиз (юқоридаги 1-қадамга қаранг).
2. Кейин киритилувчи сўзнинг биринчи белгисига қайтамиз (юқоридаги 2-қадамга қаранг).
3. Кейин қаралаётган белгини унинг ўхшаши га алмаштирамиз (пастдаги 3-қадамга қаранг), ўнгдаги биринчи бўш катакка “югурамиз” ва унга белгини ёзамиз (4-қадамга қаранг). Сўнг ўхшаш турган катакка қайтамиз (5-қадамга қаранг), аввалги белгини тиклаймиз ва ўнгда турган кейинги белгига ўтамиз (6-қадам қаранг).

a

a

b

=

A

a

b

=

A

a

b

=

a

2

3

4

5

A

a

b

=

a

a

a

b

=

a

5

6

7

a

A

b

=

a

a

A

b

=

a

a

7

8

9

…

a

a

B

=

a

a

b

a

a

b

=

a

a

b

9

12

13

30-расм.
Энди шунга ўхшаб иккинчи белги (уни га алмаштирамиз, охирида ни ёзиб қўямиз ва х.к.) ва ундан кейинги белгилардан нусха оламиз.

4. Кирувчи сўзнинг охирги белгисидан нусҳа олиб унинг ўхшашига қайтамиз (12-қадамдан сўнг), сўнг ўнгга битта катак сурилганда биз = белгисини топамиз (13-қадам). Бу кирувчи сўздан бутунлай нусҳа олиб бўлинганлиги ҳақида сигнал, шунинг учун ТМ нинг ишини тамомлаш керак.
Барча айтилганларни ҳисобга олиб ТМ учун қуйидаги дастурни оламиз:

			=
q1	,R,	,R,	x	x	x	=,L,q2	сўздан ўнг тарафда = белгисини қўйиш
q2	,L,	,L,	x	x	x	,R,q3	чапга 1-белги тагига
q3	A,R,q4	B,R,q5	, ,!	x	x	x	тахлил ва навбатдаги белгини алмаштириш
q4	,R,	,R,	,R,	x	x	a, ,q6	ўнгдан ни ёзиш
q5	,R,	,R,	,R,	x	x	b, ,q6	ўнгдан ни ёзиш
q6	,L,	,L,	,L,	a,R,q3	b,R,q3	x	қайтиш, тиклаш, кейинги белгига

31-расм.
Бу дастурда q6 ҳолатдан, уни q2 билан бирлаштириб қутилиш мумкин, бунда q2 да чапга бўш катакка ёки ва белгиларга қайтишни ҳисобга олиш керак бўлади:

			=
			...
q2	,L,	,L,	,L,	a,R,q3	b,R,q3	,R,q3	чапга гача, ёки
			...

32-расм.

Саволлар:

5. 
   Тьюринг машинасида (ТМ) автоматни силжитиш, белгиларни алмаштириш қандай бажарилади?
   
6. 
   ТМ да Р сўзнинг биринчи белгисини унинг охирига ўтказиш алгоритмини тушунтиринг.
   
7. 
   ТМ да кириш сўзидаги иккинчи белгини ўчириш программаси қандай бажарилади?
   
8. 
   Сўзга белги қўйиш алгоритмини тушунтиринг.