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

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

№ варіанта	завдання
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}. Залишити в слові Р тільки останній символ (порожнє слово не міняти).
31.	А={а, b, c}. Залишити в слові Р тільки другий символ (порожнє слово не міняти).

Лабораторна робота №2

Машини Т'юринга

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

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

Рішення.

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

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

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

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

	q1	q2	q3
a	q0ΛП	q2bП	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
a	П	q2aЛ	q4АП	q4aП	q5aП	q6aЛ
b	q2bП	q2bЛ	q5ВП	q4bП	q5bП	q6bЛ
=	Х	X	q0=	q4=П	q5=П	q6=Л
А	Х	X	Х	X	X	q3aП
В	Х	X	Х	X	X	q3bП
Λ	q2=Л	q3=П	х	q6a	q6b	х

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

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