Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
laboratorna_mashini_T_3-4.docx
Скачиваний:
11
Добавлен:
22.04.2016
Размер:
127.01 Кб
Скачать

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

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

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

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

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

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

q10 -> q20П; q20 -> q01; q11 -> q11П; q21 -> q21П.

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

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

На першому кроці діє команда: q11 -> q1

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

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

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

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

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

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

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

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

Рішення.

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

q1

q2

0

q1

q01

1

q1

q02

2

q1

q03

3

q1

q04

4

q1

q05

5

q1

q06

6

q1

q07

7

q1

q08

8

q1

q09

9

q1

q2

Λ

q2ΛЛ

q01

Пояснення.

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

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

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

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

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

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

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

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

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

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

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

Рішення.

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

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

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

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

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

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

q1

q2

q3

q4

а

q2ΛП

q2aП

q3aП

q4aП

b

q3ΛП

q2bП

q3bП

q4bП

с

q4ΛП

q2сП

q3сП

q4сП

Λ

q1ΛП

q0a

q0b

q0с

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

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

q0

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

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

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

Соседние файлы в предмете Теория алгоритмов и автоматов