Приклади на складання програм для мт

Розглянемо приклади на складання програм для МТ, щоб продемонструвати деякі типові прийоми програмування на МТ.

Для скорочення формулювання задач введемо наступні дві угоди:

• буквою Р позначатимемо вхідне слово;

• буквою А позначатимемо алфавіт вхідного слова, тобто набір тих символів, з яких і тільки яких може полягати Р (відмітимо, проте, що в проміжних і вихідному словах можуть з'являтися і інші символи).

Приклад 1. Дана машина Т'юринга із зовнішнім алфавітом А = {0, 1} (тут 0 - символ порожньоїкомірки)алфавітом внутрішніх станів Q = {q₀, q₁, q₂) і з наступною функціональною схемою (програмою) :

q₁0 ->q₂0П; q₂0 ->q₀1; q₁1 ->q₁1П; q₂1 ->q₂1П.

Запишіть складену програму (функціональну схему) побудованої машини Т'юринга у вигляді таблиці.

Подивимося, в яке слово переробить ця машина слово 101, виходячи із стандартного початкового положення. Послідовно виписуватимемо конфігурації машини при переробці нею цього слова. Маємо стандартне початкове положення:

На першому кроці діє команда: q₁1->q₁1П

В результаті на машині створюється наступна конфігурація:

На другому кроці діє команда: q₁0->q₂0Пі на машині створюється конфігурація:

Нарешті, третій крок обумовлений командою: q₂0 ->q₀1Н. В результаті його створюється конфігурація:

Ця конфігурація є завершальною, тому що машина виявилася в стані зупинки q₀.

Таким чином, початкове слово 101 перероблено машиною в слово 10101.

Приведіть послідовність конфігурацій при переробці цією машиною слова 11011, виходячи з початкового положення, при якому в стані q₁ оглядається крайня ліва комірка, в якій міститься символ цього слова (самостійно проаналізуйте кожен крок роботи машини, вказуючи, яка команда зумовила його):

Таким чином, слово 11011 перероблено машиною в слово 110111.

Приклад 2(переміщення автомата, заміна символів)

А={0,1,2,3,4,5,6,7,8,9}. Нехай Р - непорожнє слово; значить, Р - це послідовність з десяткових цифр, тобто запис ненегативного цілого числа в десятковій системі. Вимагається отримати на стрічці запис числа, яке на 1 більше числа Р.

Рішення.

Для вирішення цієї задачі пропонується виконати наступні дії:

1. Перегнати автомат під останню цифру числа.

2. Якщо це цифра від 0 до 8, то замінити її цифрою на 1 більше і зупинитися; наприклад:

3. Якщо ж це цифра 9, тоді замінити її на 0 і зрушити автомат до попередньої цифри, після чого таким же способом збільшити на 1 цю передостанню цифру; наприклад:

4.Особливий випадок: в Р тільки дев'ятки (наприклад, 99). Тоді автомат зрушуватиметься вліво, замінюючи дев'ятки на нулі, і врешті-решт виявиться під порожньою клітиною. У цю порожню клітину потрібно записати 1 і зупинитися (відповіддю буде 100) :

У вигляді програми для МТ ці дії описуються таким чином:

	q1	q2
0	q10П	q01
1	q11П	q02
2	q12П	q03
3	q13П	q04
4	q14П	q05
5	q15П	q06
6	q16П	q07
7	q17П	q08
8	q18П	q09
9	q19П	q20Л
Λ	q2ΛЛ	q01

Пояснення.

q₁- цей стан, в якому автомат "біжить" під останню цифру числа. Для цього він увесь час рухається управо, не міняючи видимі цифри і залишаючись в тому ж стані. Але тут є одна особливість: коли автомат знаходиться підостанньою цифрою, то він ще не знає про це (адже він не бачить, що записано в сусідніх клітинах) і визначить це лише тоді, коли потрапить на порожню клітину. Тому, дійшовши до першої порожньої клітини, автомат повертається назад під останню цифру і переходить в стан q₂ (управо рухатися вже не потрібно).

q₂ - цей стан, в якому автомат додає 1 до тієї цифри, яку бачить в даний момент. Спочатку це остання цифра числа; якщо вона - в діапазоні від 0 до 8, то автомат замінює її цифрою, яка на 1 більше, і зупиняється. Але якщо це цифра 9, то автомат замінює її на 0 і зрушується вліво, залишаючись в стані q₂. Тим самим, він тепер додаватиме 1 до попередньої цифри. Якщо і ця цифра дорівнює 9, то автомат замінює її на 0 і зрушується вліво, залишаючись в колишньому стані q₂, оскільки повинен виконати ту ж саму дію - збільшити на 1 видиму цифру. Якщо ж автомат зрушився вліво, а у видимій клітині немає цифри (а "порожньо"), то він записує сюди 1 і зупиняється.

Відмітимо, що для порожнього вхідного слова наша задача не визначена, тому на цьому слові МТ може поводитися як завгодно. У нашій програмі, наприклад, при порожньому вхідному слові МТ зупиняється і видає відповідь 1.

Перевірити роботу на словах: 890, 49387.

Приклад 3(аналіз символів)

А={а, b, c}. Перенести перший символ непорожнього слова Р в його кінець. Наприклад:

Рішення.

Для вирішення цієї задачі пропонується виконати наступні дії:

1. Запам'ятати перший символ слова Р, а потім стерти цей символ.

2. Перегнати автомат управо під першу порожню клітину за Р і записати в неї символ, який запам'ятали.

Як "бігати" управо, ми вже знаємо з попереднього прикладу. А ось як запам'ятати перший символ? Адже в МТ немає іншого пристрою, що запам'ятовує, окрім стрічки, а запам'ятовувати символ в якійсь клітині на стрічці безглуздо: як тільки автомат зрушиться вліво або вправо від цієї клітини, він тут же забуде цей символ. Що робити?

Вихід тут такий - потрібно використовувати різні стани автомата. Якщо перший символ - це а, те потрібно перейти в стан q₂, в якому автомат біжить управо і записує у кінці а. Якщо ж першим був символ b, тоді потрібно перейти в стан де робиться все те ж саме, тільки у кінці записувати символ b. Якщо ж першим був символ с, тоді переходимо в стан q₄, в якому автомат дописує за вхідним словом символ _с. Отже, то, яким був перший символ, ми фіксуємо переводом автомата в різні стани. Це типовий прийом при програмуванні на МТ.

З урахуванням сказаного програма буде такою:

	q1	q2	q3	q4
а	q2ΛП	q2aП	q3aП	q4aП
b	q3ΛП	q2bП	q3bП	q4bП
с	q4ΛП	q2сП	q3сП	q4сП
Λ	q1ΛП	q0a	q0b	q0с

Розглянемо поведінку цієї програми на вхідних словах, що містять не більше одиного символу. При порожньому слові, яке є "поганим" для задачі, програма зациклиться - автомат, знаходячись в стані q₁ і потрапляючи увесь час на порожні клітини, нескінченно переміщатиметься управо. (Звичайно, в цьому випадку програму можна було б зупинити, але ми спеціально зробили зациклення, щоб продемонструвати таку можливість.)

Якщо ж у вхідному слові рівно один символ, тоді автомат зітре цей символ, зрушиться на одну клітину управо і запише в неї цей символ:

q₀

Таким чином, слово з одного символу просто зрушиться на клітину управо. Це допустимо. Адже клітини стрічки не нумеровані, тому місце розташування слова на стрічці ніяк не фіксується і переміщення слова вліво або управо помітити не можна. У зв'язку з цим не вимагається, щоб вихідне слово обов'язково знаходилося в тому ж місці, де було вхідне слово, результат може виявитися і лівіше, і правіше за це місце.

Приклад 4(порівняння символів, стирання слова)

А={а, b, c}. Якщо перший і останній символи (непорожнього) слова Р однакові, тоді це слово не міняти, а інакше замінити його на порожнє слово.

Рішення.

Для вирішення цієї задачі пропонується виконати наступні дії:

1. Запам'ятати перший символ вхідного слова, не стираючи його.

2. Перемістити автомат під останній символ і порівняти його з тим, що запам'ятався. Якщо вони рівні, то більше ні чого не робити.

3. Інакше знищити усе вхідне слово.

Як запам'ятовувати символ і як переганяти автомат під останній символ слова, ми вже знаємо з попередніх прикладів. Стирання ж вхідного слова реалізуєтьсязаміною усіх його символів на символ Λ. При цьому, раз вже автомат виявився у кінці слова, переміщатимемо автомат справа наліво до першої порожньої клітини.

Ці дії описуються наступною програмою для МТ (нагадаємо, що хрестик в елементі таблиці означає неможливість появи відповідної конфігурації при виконанні програми) :

	q1	q2	q3	q4	q5	q6	q7	q8
a	q2a	q2aП	q0a	q4aП	q8a	q6aП	q8a	q8ΛЛ
b	q4b	q2bП	q8b	q4bП	q0b	q6bП	q8b	q8ΛЛ
c	q6c	q2cП	q8c	q4cП	q8c	q6cП	q0c	q8ΛЛ
Λ	q0Λ	q3ΛЛ	х	q5ΛЛ	х	q7ΛЛ	х	q0Λ

Перевірити роботу на словах: aabcbc, cbbaa.

Приклад 5(видалення символу із слова)

А={а, b}. Видалити із слова Р його другий символ, якщо такий є.

Рішення.

Здавалося б, це завдання вирішити просто: потрібно зрушити автомат під клітину з другим символом і потім очистити цю клітину:

Проте нагадаємо, що усередині вихідного слова не повинно бути порожніх клітин. Тому після видалення другого символу потрібно "стискувати" слово, перенісши перший символ на одну клітину управо. Для цього автомат повинен повернутися до першого символу, запам'ятати його і стерти, а потім, знову зрушившись управо, записати його в клітину, де був другий символ. Проте початковий "похід" управо до другого символу, щоб його стерти, і наступне повернення до першого символу є зайвими діями: яка різниця - переносити перший символ в порожню клітину або в клітину з якимсь символом? Тому відразу запам'ятовуємо перший символ, стираємо його і записуємо замість другого символу:

У вигляді програми для МТ усе це записується так:

	q1	q2	q3
а	q2ΛП	q0а	q0b
b	q3ΛП	q0а	q0b
Λ	q0Λ	q0а	q0b

Перевірити роботу на словах:aabbba, ababab.