МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна робота №1 Програмування машин Тьюрінга № варіанту = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 30 + 1= =(14+84)%30+1=98%30+1=8+1=9 Львів – 2012 1. Мета роботи Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга. 2. Постановка задачі Загальна частина: Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване. Скласти програму для мaшини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення). Відлагодження і тестування програми провести в середовищі емулятора машини Тьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ. 9. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів bc на символ a. 3.Словесний опис алгоритму Переглядаємо вхідне слово зліва направо до порожньої комірки або до першого символу b. В першому випадку символ bc не входить в слово P, тому нічого не робимо. В іншому випадку треба на місце символу с записати символ а , а потiм переміщаємо початок слова P (від знайденого символу bc до першого символу) на одну позицію вправо. Якщо через
позначити стан, у якому в комірку треба записати символ x, який перебував раніше в комірці зліва.Для цього потрібно виконати такт
, у якому об'єднані наступні три дії: - по-перше, в комірку записується символ x, взятий із комірки зліва; - по-друге, каретка переміщується вправо (під комірку, в яку потім треба буде записати тільки що замінений символ y); - по-третє, каретка переходить в стан
, у якому вона і буде виконувати цей запис. Повторення таких тактів у циклі і приведе до переміщення вправо на одну позицію початкових символів вхідного слова. Цей цикл повинен закінчитись, коли в черговій комірці виявиться символ a або
(y=a або y=
), а на початку циклу можна вважати, що на місце першого символу зліва переноситься символ «порожньо» (x=
). 4. Алгоритм у вигляді програми для МТ 4.1. Повна таблиця Q A a0 a b c Пояснення  q1 q0 a0 q1 a R q2 b R q1 c R аналіз вхiдного слова до першого b , розгалуження  q2 q0 a0 q1 a R q1 b R q3 a L якщо наступний символ с то спочатку q3 а потiм q4  q3  q4 a L q4 b L q4 c L переміститись наліво  q4 q8a0L q5 a L q6 b L q7 c L розгалуження  q5  q3 a L q3 a L q3 a L запис a справа  q6  q3 b L q3 b L q3 b L запис b справа  q7  q3 c L q3 c L q3 c L запис c справа  q8  q1 a0 L q1 a0 L q1 a0 L a0 замiсть першого символа   4.2. Скорочена таблиця Q A a0 a b c Пояснення  q1 q0  R q2 R  R аналіз вхiдного слова до першого b , розгалуження  q2 q0  R q1 R q3 a L якщо наступний символ с то спочатку q3 а потiм q4  q3  q4 L q4 L q4 L переміститись наліво  q4 q8a0L q5 L q6 L q7 L розгалуження  q5  q3 L q3 a L q3 a L запис a справа  q6  q3 b L q3 L q3 b L запис b справа  q7  q3 c L q3 c L q3 L запис c справа  q8  q1 a0 L q1 a0 L q1 a0 L a0 замiсть першого символа   5.Ефективність алгоритму 5.1. Часова складність Запустивши покроково (F8) програму на виконання можна порахувати, що кількість виконаних тактів по переробці слова acbccb дорівнює 20, тобто часова складність T=20. 5.1. Місткісна складність Можна зауважити, що в процесі роботи використовуються комірки стрічки з номерами від 2 до 7 , тобто місткісна складність М=6. 5.1. Програмна складність Табличне представлення МТ містить 32 заповнені комірки, отже програмна складність цієї МТ дорівнює Р=32. 6. Результати виконання програми