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

3 мисол. Белгиларни таққослаш, сўзларни ўчириш.
F={a,b,c}. Агар Р бўш бўлмаган кириш сўзининг биринчи ва охирги белгилари бир хил бўлса, унда бу сўзни алмаштирманг, акс ҳолда уни бўш сўзга алмаштиринг.
Ечилиши.
1. Кириш сўзидаги биринчи белгини ўчирмасдан уни сақлаб қўйиш.
2. Автоматни охирги белги остига олиб бориш ва уни хотирадаги белги билан таққослаш.Агар улар тенг бўлса бошқа ҳеч қандай иш бажармаслик керак.
3. Акс ҳолда барча кириш сўзини ўчириб ташлаш.
Белгини қандай излаш кераклигини ва автоматни қандай қилиб кириш сўзининг охирги белгисини остига олиб бориш кераклигини олдинги мисолдан биламиз. Кириш сўзини ўчириш деганда, унинг барча элементларини Λ белгисига алмаштириш кераклигини ҳам биламиз. Шу билан бирга, агар автомат сўз охирига жойлашган бўлса, автоматни ўнгдан чапга томон то биринчи бўш катаккача силжита оламиз. Бу амаллар ТМ учун қуйидаги программа орқали ёзилади (эслатиб ўтамиз, жадвал ячейкасидаги крестиклар программанинг бажарилишида мос конфигурацияларнинг рўй бериши мумкин эмаслигини билдиради):

12-расм. ТМ да кириш сўзидан белгини ўчиришнинг бажарилиши.
4-мисол.
A={a,b}. Р сўзидан унинг иккинчи элементини ўчиринг, албатта, агар шундай белги бор бўлса.
Ечилиши:
Кўринишдан бу масалани ечиш жуда оддий:автоматни иккинчи белги остига олиб келиш керак ва бу катакни тозалаш керак.

13-расм. ТМ да кириш сўзида иккинчи белгини ўчиришнинг бажарилиши.
Лекин эслатиб ўтамизки, чиқиш сўзининг ичида бўш катаклар бўлмаслиги керак. Шунинг учун иккинчи белгини ўчиргандан сўнг, биринчи белгини ўнг томонга битта катакка ўтказиш билан, сўзни “сиқиш” керак. Бунинг учун автомат биринчи белгига қайтиши керак, уни эслаб қолиши ва ўчириши лозим. Сўнгра яна ўнгга томон силжиб, иккинчи белгининг жойига буни ёзиб қўйиши керак. Лекин бошланғич ўнгга томон иккинчи белги томонга уни ўчириш учун “юриш” ва навбатдаги биринчи белгига қайтиш ортиқча амаллар бўлиб ҳисобланади; Биринчи белгини бўш катакка олиб ўтиш ёки катакка бирор белги билан ўтишнинг нима фарқи бор? Шунинг учун биринчи белгини бирданига эслаб қолинади ва уни ўчириб иккинчи белги ўрнига ёзиб қўйилади:

14-расм. ТМ да кириш сўзидаги иккинчи белгини ўчириш.
ТМ учун программа кўриниши қуйидагича бўлади:

15-расм. ТМ да кириш сўзидаги иккинчи белгини ўчириш программаси.