Індивідуальні завдання

Записати МТ у вигляді програми, та навести перевірку роботи програми на двох словах (q₁- на початку слова).

№ варіанта	завдання
1, 5.	А={а, b, c}. Приписати ліворуч до слова Р символb(Р →bР).
2, 6.	А={а, b, c}. Приписати справа до слова Р символиbс (Р → Рbс).
3, 7.	А={а, b, c}. Замінити наакожен другий символ в слові Р.
4, 8.	А={а, b, c}. Залишити в слові Р тільки перший символ (порожнє слово не міняти).
9, 15.	А={а, b, c}. Залишити в слові Р тількидругийсимвол (порожнє слово не міняти).
10, 16.	А={а, b, c}. Залишити в слові Р тільки останній символ (порожнє слово не міняти).
11, 17.	А={а, b, c}. Приписати ліворуч до слова Р символa(Р →aР).
12, 18.	А={а, b, c}. Замінити наbкожен другий символ в слові Р.
13, 19.	А={а, b, c}. Залишити в слові Р тількипершийсимвол (порожнє слово не міняти).
14, 20.	А={а, b, c}. Приписати справа до слова Р символиас (Р → Рас).
21, 25.	А={а, b, c}. Залишити в слові Р тільки останній символ (порожнє слово не міняти).
22, 26.	А={а, b, c}. Приписати ліворуч до слова Р символс(Р →сР).
23, 27.	А={а, b, c}. Приписати справа до слова Р символиаb(Р → Раb).
24, 28.	А={а, b, c}. Замінити наскожен другий символ в слові Р.
29.	А={а, b, c}. Залишити в слові Р тільки перший символ (порожнє слово не міняти).
30.	А={а, b, c}. Залишити в слові Р тількидругийсимвол (порожнє слово не міняти).

Лабораторна робота №4 Програма машини т'юринга

Сама по собі МТ нічого не робить. Для того, щоб змусити її працювати, потрібно написати для неї програму. Ця програма записується у вигляді наступної таблиці:

А\Q	q1	…	qj	…	qm
А1
А2
Аi				q'A' [С, П, Л]
Аn
Λ

Ліворуч перераховуються усі символи (у тому числі і Λ), в яких може знаходитися автомат, згори – усі стани, які автомат може бачити на стрічці. (Які саме символи і стани вказувати в таблиці – визначає автор програми.) На перетинах (у елементах таблиці) вказуються ті такти, які повинен виконати автомат, коли він знаходиться у відповідному стані і бачить на стрічці відповідний символ.

В цілому таблиця визначає дії МТ при усіх можливих конфігураціях і тим самим повністю задає поведінку МТ. Описати алгоритм у вигляді МТ – означає пред'явити таку таблицю.

(Зауваження. Часто МТ визначають як таку що складається із стрічки, автомата і програми, тому при різних програмах виходять різні МТ. Ми ж вважатимо, у дусі сучасних комп'ютерів, що МТ одна, але вона може виконувати різні програми).

q₁- на початку слова, в пустих комірках символ Λ.

Приклад 6 (стискування слова)

А={а, b, c}. Видалити із слова Р перше входження символу а, якщо такий є.

Рішення.

У попередньому прикладі ми переносили на позицію управо тільки один символ. У цьому ж прикладі ми в циклі переноситимемо управо усі початкові символи bіcвхідного слова - до першого символуаабо до порожньої клітини:

Центральний момент тут - як перенести символ хз лівої клітини в чергову клітину, де знаходиться деякий символу, щоб потім цей символуможна було перенести в праву клітину? Якщо черезq_хпозначити стан, в якому у видиму клітину потрібно записати символх, що знаходився раніше в клітині ліворуч, тоді цю дію можна зображувати так:

Для цього пропонується виконати такт q_уxП, в якому об'єднані слі­дуючі три дії: по-перше, у видиму клітину записується символх, узятий з клітини ліворуч; по-друге, автомат зрушується управо – під клітину, в яку потім потрібно буде записати тільки що замінений символу; по-третє, автомат переходить в станq_ув якому він і виконуватиме цей запис.

Повторення таких тактів в циклі і приведе до зрушення управо на одну позицію початкових символів вхідного слова. Цей цикл повинен закінчитися, коли в черговій клітині опиниться символ аабо Λ (у = а абоу = Λ), а на початку циклу можна вважати, що на місце першого символу ліворуч переноситься "порожній" символ (х = Λ). У результаті виходить наступна програма для МТ:

	q1	q2	q3
A	q0ΛП	q0bП	q0с
B	q2ΛП	q2bП	q2сП
C	q3ΛП	q3bП	q3сП
Λ	q0Λ	q0b	q0с

У цій програмі слід звернути увагу на такт q₀ΛП, який виконується в конфігурації <а,q₁>, тобто коли першим символом вхідного слова єа. Ясно, що потрібно просто стерти цей символ і зупинитися. Проте в цьому такті вказано ще і зрушення управо. Навіщо? Нагадаємо, що у момент останову автомат повинен знаходитися під вихідним словом (під будь-яким його символом), тому ми і зрушуємо автомат з порожньої клітини на клітину з першим символом вихідного слова, який у вхідному слові був другим.

Перевірити роботу на словах: abbcaa, cbccbaa

Приклад 7 (вставка символу в слово)

А={а, b, c}. Якщо Р - непорожнє слово, то за його першим символом вставити символ а.

Рішення.

Ясно, що між першим і другим символами слова Р потрібно звільнити клітину для нового символу а. Для цього потрібно перенести на одну позицію влівоперший символ (на старому місці його можна не видаляти), а потім, повернувшись на старе місце, записати символ а:

Перенесення символу на одну позицію вліво аналогічне перенесенню символу управо, про що говорилося в двох попередніх прикладах, тому приведемо програму для МТ без додаткових коментарів. Відмітимо лише, що в станах q₂,q₃іq₄автомат може бачити тільки порожню клітину, а встані q₅він обов'язково бачить перший символ вхідного слова, але не порожню клітину.

	q1	q2	q3	q4	q5
a	q2aЛ	х	х	х	q0a
b	q3bЛ	х	х	х	q0a
c	q4cЛ	х	х	х	q0a
Λ	q0Λ	q5aП	q5bП	q5cП	х

Перевірити роботу на словах: abbcc, caabbc

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

А = {а, b, c}. Вставити в слово Р символ а за першим входженням символу c, якщо такий є.

Рішення.

Переглядаємо вхідне слово зліва направо до порожньої клітини або до першого символу с. В першому випадкусне входить вР, тому нічого не робимо. У другому випадку потрібно звільнити місце для символу а, що вставляється, для чого зрушуємо початок словаР(від першого символу до знайденого символус) на одну позицію вліво. При цьому здійснюємо таке зрушення справа наліво – від символусна початок слова, раз вже автомат знаходиться під цим символом. Крім того, щоб потім не повертатися до позиції, що звільнилася, починаємо це зрушення із записуазамість знайденого символус. Оскільки це циклічне зрушення вліво реалізується аналогічно циклічному зрушенню управо з прикладу 5, то не пояснюватимемо його, а відразу приведемо програму для МТ:

	q1	q2	q3	q4
а	q1аП	q2аЛ	q2bЛ	q2cЛ
b	q1bП	q3аЛ	q3bЛ	q3cЛ
c	q4аЛ	q4аЛ	q4bЛ	q4cЛ
Λ	q0ΛЛ	q0а	q0b	q0c

Перевірити роботу на словах: bbcbbc, abcabc

Приклад 9 (формування слова на новому місці)

А = {а, b, c}. Видалити з Р усі входження символу а.

Рішення.

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

Конкретно пропонується виконати наступні дії:

1. Вихідне слово будуватимемо праворуч від вхідного. Щоб розмежувати ці слова, відокремимо їх деяким допоміжним символом, наприклад знаком =, відмінним від усіх символів алфавіту А(див. крок 1). (Нагадаємо, що на стрічці можуть бути записані не лише символи з алфавіту вхідного слова.)

2. Після цього повертаємося на початок вхідного слова (див. крок 2).

3. 

   Тепер наше завдання - перенести в циклі усі символи вхідного слова, окріма, управо за знак = у формоване вихідне слово.

Для цього аналізуємо перший символ вхідного слова. Якщо це а, тоді стираємо його і переходимо до наступного символу (див. крок 3). Якщо ж перший символ - це bабоc, тоді стираємо його і "біжимо" управо до першої порожньої клітини (див. крок 4), куди і записуємо цей символ (див. крок 5).

Знову повертаємося наліво до того символу, який став першим у вхідному слові, і повторюємо ті ж самі дії, але вже по відношенню до цього символу (див. кроки 6-9).

4. Цей цикл завершується, коли при поверненні наліво ми побачимо як перший символ знак =. Це ознака того, що ми повністю проглянули вхідне слово і перенесли усі його символи, відмінні від а, у формоване справа вихідне слово. Потрібно цей знак стерти, зрушитися управо під вихідне слово і зупинитися (див. крок 10).

З урахуванням усього сказаного і будуємо програму для МТ. При цьому відмітимо, що окрім символіва, bіcв процесі рішення задачі на стрічці з'являється знак =, тому в таблиці має бути передбачений стовпець і для цього знаку.

	q1	q2	q3	q4	q5
a	q1aП	q2aЛ	q3ΛП	q4aП	q5aП
b	q1bП	q2bЛ	q4ΛП	q4bП	q5bП
c	q1cП	q2cЛ	q5ΛП	q4cП	q5cП
=	x	q2=Л	q0ΛП	q4=П	q5=П
Λ	q2=	q3ΛП	x	q2b	q2c

Перевірити роботу на словах: aacabac, bbbaccc

Приклад 10 (фіксація місця на стрічці)

А = {а, b}. Подвоїти слово Р, поставивши між ним і його копією знак =. Наприклад:

Рішення.

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

Проте є і відмінність: копійовані символи вхідного слова не видаляються, і це призводить до наступної проблеми. Записавши справа копію чергового символу, ми потім повинні повернутися до вхідного слова в позицію цього символу і потім зрушитися управо до наступного символу, щоб скопіювати вже його. Але як дізнатися, в яку позицію вхідного слова потрібно повернутися? Наприклад, звідки ми знаємо в нашому прикладі, що після копіювання першого символуами повинні повернутися саме до першого символу вхідного слова, а не до другого або третього? У попереднійзадачі ми завжди поверталися до першого з символів вхідного слова, що залишилися, а тепер ми зберігаємо усі символи, тому незрозуміло, які символи ми вже скопіювали, а які ще ні. Відмітимо також, що в МТ коміркистрічки ніяк не нумеруються, немає в МТ і лічильників, які дозволили б визначити, скільки символів ми вже скопіювали.

У загальному вигляді проблема, з якою ми зіткнулися, наступна: як зафіксувати на стрічці деяку позицію, в якій ми вже були і до якої пізніше повинні повернутися? Зазвичай ця проблема вирішується так. Коли ми опиняємося в цій позиції вперше, то замінюємо символ, що знаходиться в ній, на його двійник - на новий допоміжний символ, причому різні символи замінюємо на різні двійники, наприклад ана А іbна В. Після цього ми виконуємо якісь дії в інших місцях стрічки. Щоб потім повернутися до нашої позиції, потрібно просто відшукати на стрічці ту клітину, де знаходиться символ А або В. Потім в цій клітині можна відновити колишній символ, якщо нам більше не потрібно фіксувати цю позицію (саме для відновлення колишнього символу і потрібно було замінювати різні символина різні двійники).

Скористаємося цим прийомом в нашійзадачі, виконуючи наступні дії:

1. Як вже сказано, спочатку записуємо знак = за вхідним словом (див. крок 1 вище).

2. Потім повертаємося під перший символ вхідного слова (див. крок 2 вище).

3. Далі замінюємо видимий символ ана двійник А (див. крок 3 нижче), "біжимо" управо до першої вільної клітини і записуємо в неї символа(див. крок 4). Після цього повертаємося вліво до клітини з двійником А (див. крок 5), відновлюємо колишній символаі зрушуємося управо до наступного символу (див. крок 6).

Тепер аналогічним чином копіюємо другий символ (замінюємо його на А, в кінець дописуємо аі так далі) і усі наступні символи вхідного слова.

4. Коли ми скопіюємо останній символ вхідного слова і повернемося до його двійника (після кроку 12), то потім після зрушення на одну позицію управо ми потрапимо на знак = (крок 13). Це сигнал про те, що вхідне слово повністю скопійоване, тому роботу МТ потрібно завершувати.

З урахуванням усього сказаного отримуємо наступну програму для МТ:

	q1	q2	q3	q4	q5	q6
а	q1aП	q2aЛ	q4АП	q4aП	q5aП	q6aЛ
b	q1bП	q2bЛ	q5ВП	q4bП	q5bП	q6bЛ
=	Х	X	q0=	q4=П	q5=П	q6=Л
А	Х	X	Х	X	X	q3aП
В	Х	X	Х	X	X	q3bП
Λ	q2=Л	q3ΛП	х	q6a	q6b	х

Відмітимо, що в цій програмі можна позбавитися від стану якщо об'єднати його із станом передбачивши в повернення вліво як до порожньої клітини, так і до символів А і В:

Перевірити роботу на словах: bbaba, aabbaa