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

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

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

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

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

Приклад 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):

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

Пояснення.

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₄, в якому автомат дописує за вхідним словом символ _с. Отже, то, яким був перший символ, ми фіксуємо переводом автомата в різні стани. Це типовий прийом при програмуванні на МТ.

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

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

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

q0

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

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

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

Рішення.

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

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

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

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

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

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

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

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

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

Рішення.

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

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

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

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

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

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

ЛАБОРАТОРНА РОБОТА №4

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

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

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

Рішення.

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

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

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

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

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

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

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

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

Рішення.

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

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

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

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

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

Рішення.

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

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

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

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

Рішення.

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

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

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

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

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

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

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

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

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

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

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

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

Рішення.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск по сайту: