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

6-мисол. Сўзга белги қўйиш.
A={a,b,c}. Агар Р-бўш сўз бўлмаса, унда унинг биринчи белгисидан сўнг а белгисини қўйинг.
Ечилиши:
Ўз-ўзидан тушунарлики, Р сўзининг биринчи ва иккинчи белгилари орасига янги а белгисини қўйиш учун битта катак ажратиш керак. Бунинг учун биринчи белгини битта позиция чапга ўтказиш керак (уни эски жойида ҳали ўчирмаслик керак), кейин, эски жойга қайтгач а белгисини ёзиш керак:

19-расм. ТМ да кириш сўзининг биринчи белгисидан сўнг а белгисини қўйиш.

Белгини битта позиция чапга ўтказиш худди белгини битта позиция ўнгга ўтказиш сингари бўлади, олдинги иккита мисолдаги айтиб ўтилганидек, шу сабабли ТМ учун ёзилган программани қўшимча изоҳларсиз келтирамиз. Фақат таъкидлаб ўтамизки, q2, q3 ва q4 ҳолатларда автомат фақат бўш катакни кўриши мумкин, лекин q5 ҳолатда эса у бўш катакни эмас, албатта кириш сўзининг биринчи белгисини кўради.

	a	b	c	Λ	Изоҳ
q1	,L,q2	,L,q3	,L,q4	, ,!	1-белгини чапга ўтказиш учун уни таҳлил қилиш
q2	x	x	x	a,R,q5	чап томондан а ни ёзиб қўйиш
q3	x	x	x	b,R,q5	чап томондан b ни ёзиб қўйиш
q4	x	x	x	c,R,q5	чап томондан c ни ёзиб қўйиш
q5	, ,!	a, ,!	a, ,!	x	Олдинги 1-белгини а га алмаштириш

20-расм. ТМ да кириш сўзининг 1- белгисидан сўнг а белгисини қўйиш программаси.