Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Емуляція на ПЕОМ машин Тюрінга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Теорія
Предмет:
Інші
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра АСУ
Звіт
з лабораторної роботи №3
з дисципліни
“ Теорія алгоритмів і математичні основи
представлення знань ”
на тему:
Емуляція на ПЕОМ машин Тюрінга
Львів-2007
Мета лабораторної роботи - емуляцiя на ПЕОМ машин Тюрінга і констроювання програм для них.
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Для засвоєння поняття машин Тюрінга і освоєння конструювання Т-машин (єх програм) необхідно в певній мірі автоматизувати тестування та відладку програм Т-машин (Т-програм).
Для цього необхідно в данній лабораторній роботі емулювати на ПЕОМ машину Тюрінга, якаб по заданій Т-програмі Пт і входу w імітувала обчислення функціє F, що задається Пт.
В основі алгоритмічноє системи Тюрінга лежить поняття абстрактнго автомата - машини Тюрінга (Т-машини). В літературі наведено багато варіантів визначення Т-машини. Ми розглядатемемо найбільш поширений варіант цієє машини.
I. Нехай задано вхідний алфавіт Eвх = {a1,..,an},внутрішній алфавіт Eвн = {b1,..,br},і E є об"єднання алфавітів Eвх і Eвн, причому перетин Eвн і Eвх є пустою множиною. E будемо називати повним алфавітом. Елементи алфавітів називаються буквами або літерами.
Через E* позначимо множину всіх слів в алфавіті E, включаючи пусте слово e, а, відповідно, через E*вх - множину всіх вхідних слів.
Довільну скінченну підмножину Q = {q0,q1,..,qm} деякої нескінченноє множини Q^ = {..,q(-1),q0,..qm,..} будемо називати множиною міток, а єє елементи - мітками.
Будемо вважати, що перетин Q і E є пустою множиною.
Командю Тюрінга (Т-командою ) називається вираз вигляду
q d -> q'd'r (1)
де q і q' - мітки із Q, d і d' - літери із E, а r приймає значення одного із трьох чисел : -1,0,+1. Пара qd із (1) називається Т-міткю. Програмою Тюрінга (Т-прграмою) називається двільна скінченна сукупність Пт Т-команд
U0
U1 (2)
..
Um
в якій різні команди мають різні Т-мітки остання умова означає, що кожна Т-команда
Ui = ( qi di -> qi'di'ri ) (3)
в Пт однзначно визначається по своєй Т-мітці.
Машиною Тюрінга називається довільний набір Мт = (Q,E,q^,#,Пт), --------------- ---------------
де:
Q - множина міток;
E -об'єднання вхідного Eвх та внутрішнього Eвн алфавітів;
q^ - виділений елемент із Q, який називається початковою міткою Мт;
# - виділений елемент із Eвн;
Пт - Т-програма.
Коли кманда q d -> q'd'r входить в програму Пт Т-машини Мт, тді мітка q і Т-мітка (q d) називаються прміжковими мітками йієє машини. Всі непромщжкві мітки і Т-мітки називаються кінцевими мітками Т-машини Мт.
Станом Т-машини (Т-станом) називається довільна нескінченна в обидва боки послідовність
t = ...d(-2) d(-1) q d(0) d(1) d(2)... (4)
де d(j) (j = ...-2,-1,0,1,2,...) - літери із E, а q - мітка із Q.
Для машини Мт Т-стан (4) називається : а) початковим, коли q = q^
б) проміжковим, коли < q d(0) > - проміжкова Т-мітка; в) кінцевим, коли < q d(0) > - кінцева Т-мітка Мт.
Множину всіх станів Т-машини Мт позначимо через Dм.
Тепер визначимо функцію переходів Fт : Dм --> Dм.
Коли Т-мітка <q d(0)> - кінцева в стані (4), то Fт(t) = t.
Нехай <q d(0)> - проміжова Т-мітка стану (4). Тоді в програмі Пт знайдеться одна і тільки одна команда вигляду q d(0) -> --> q'd'r. Під дією цієї команди Т-стан t переходить в стан t' = Fт(t). Залежно від r = +1,0,-1 значення tr = Fт(t) приймє вигляд :
t+ = ...d(-2) d(-1) d' q' d(1) d(2)...
t0 = ...d(-2) d(-1) q' d' d(1) d(2)... (5)
t- = ...d(-2) q' d(-1) d' d(1) d(2)...
Із (5) випливає,що при r = +1,0,-1 вираз "q d(0)" в стані(4), відповідно,замінюється на вирази " d' q' ", "q' d' " i " q' d(-1) d'"
Тепер опишемо, яким чином кожній Т-машині Мт можна співставити функцію f[Мт] : E*вх --> E*.
Далі через /d/ = ...ddddd... будемо позначати Нескінченну послідовність літери d із E.
Нехай w - довільне слово із E*вх. Опишемо функціонування Мт на v.Введемо початовий стан t[0] Т-машини Мт ,де
t[0] = /#/q^ w /#/.
Траєкторією Т-машини Мт (на вході w) називається нескінченна послідовність T^ = t[0],t[1],t[2]..., де t[0] - початковий стан, і для кожного натурального i > = 0,
t[i+1] = Fт( t[i+1] ) .
Можливі два випадки :
1) знайдеться таке s, що t[s] = /#/q' v /#/. -кінцевий стан, а для всіх j (0 < = j < = s-1) t[j] - проміжковий стан Мт в послідовності T^;
2)всі стани в послідовності T^ - проміжкові.
В перщому випадку будемо вважати,що f[Мт](w) = v, а в другому коли Мт циклює, вважатимемо, що f[Мт](w) = @, тобто її значення не визначено.
Аналогічно можна вважати, що Мт обчислює предикат
P[Мт] : E*вх --> {T,F},
якщо E*вн містить множину {T,F}, і : а) P[Мт](w) = T,якщо в кінцевому стані t[s] = /#/q' v /#/ слово v = T;
б) P[Мт](w) = F, якщо в кінцевому стані t[s] = /#/q' v /#/ слово v = F;
d) P[Мт](w) = @, якщо Мт циклює на w.
Функціонування Т-машини , її Т-стани і обчислення функції переходів Fт можна описувати на її "фізичній" моделі ,тобто можна трактувати на мові "стрічок", "блоку управління","головки" і т.п.
При цій трактовці Т-машина Мт складається із потенційно нескінченноє ( в обидва боки ) стрічки, блоку управління (У-блоку) і головки, що може пересуватися вздовж стрічки. Стрічка розділена на комірки, в яких у кожний момент часу записно певний символ із E.
Головка здійснює читання і запис літер на стрічці. В кожний момент головка може сприймати одну і тільки одну комірку стрічки. В процесі роботи Т-машини Мт може стояти на місці, або пересуватися вправо і ліво по стрічці. Крім того, в головці в кожний момент записана деяка мітка із Q.
У-блок містить Т-програму Пт, і керує роботою Т-машина Мт.
─────────────────────────────────────
...|d(-2)| d(-1)| d(0)| d(1)| d(2)|...
──────────────────────────────────────-
┌─ ─┐
│ q │
├─────
──────────────────────┐
│ У-БЛОК │
│ Т-програма Мт │
└──────────────────────┘
В на кожному кроці функціонування Т-машини Мт голвка передає У-блоку символ d(0), що вона спостерігає на вхідній стрічці, а також мітку q , що зберігається в головці. В прграмі Пт У-блок знаходить команду з Т-міткою <q d(0)> (нехай вона має вигляд q d(0) -> q'd'r), потім записує на стрічку замість d(0) символ d', в голвку - стан q', і в залежності від значення r = +1,-1,0 зсуває,відповідно,головку вправо, вліво ,або залишає на місці. Т-машина фукцінує до тих пір, поки в головку не У-блок не зустріне кінцеву Т-мітку Мт.Інакше вона зациклюється.
Часткові або всюдиозначенні функцію g : E*вх -->E*вх, яка задана на множині слів довільного алфавіту E , або предикат P : E* --> {T,F}, будемо називати Т-функцією (Т-предикатом), якщо існує Т-машщина Мg(Мp), що обчислює g (P).
Як відомо [1], клас всіх Т-функцій містиця в класі всіх функцій,що обчислюються нормальними алгоритмами, а сам він містить у собі клас всіх функцій, що обчислюються операторними алгоритмами.
Приклад Т-машини і опис її фукціонування наведено в розділі VI данної інструкції.
II. ПОРЯДОК РОБОТИ
1. Вивчити визначення алфавітів машин Тюрінга, Т-команд і Т-програм, а також механізм обчислення Т-машиною Тf функції f :
E* -->E*.
2. Розробити алгоритм емуляції нормальних алгоритмів на ПЕОМ. Засобами мови Паскаль або Си реалiзувати процедуру , що емулює на ПЕОМ функціонування Т-машини, створивши відповідні типи даних, що забезпечать ввід інформації, а також візщуалізації результатів роботи Мт.Відладити емулятор Т-машин.
3. По виданому завданню ( конкретній функціє f ) скласти Т-програму Пf, що реалізує функцію f.
4. За допомогою емулятора Т-машин відлагодити М-програму Пf.
5. Здати викладачевi розроблені процедури, продемонструвавши їх працездатнiсть на конкретних вхідних даних.
6. Проаналізувати результати роботи емулятора та Пf.
7. Оформити звіт по лабоораторній роботі.
3) v(w,s1,s2) = s3s2s4, якщо w = s3s1s4;
4) перехід від n до n+1 в десятковій системі числення;
5) перетворення унарного запису числа в десятковий.
6) додавання десяткових чисел
7) віднімання десяткових чисел
VI. КОНТРОЛЬНИЙ ПРИКЛАД
Необхідно побудувати машину Тюрінга М1, яка реалізує функцію f1(x) = x + 1, вважаючи ,що числа x і значення f1(x) задаються в десятковій системі счислення, тобто числа x і f1(x) задаються словом у алфавіті E1вх = {0,1,..,8,9},причому вважається,що число нуль може задаватися літерою 0 із E1вх, або пустим словом е = '' із E*вх.
При конструюванні Т-машини будемо номерувати єє команди, щоб потім можна було по кроках описати її роботу.
Т-машина,що реалізує f1 має вигляд М1 = (Q1,E1,q^,#,П1),де Q1 = {q^,q1,Я}, E1вн = {#}, а Т-програма П1 наведена нижче :
1) q^ 0 --> q^ 0 +1 12) q1^ 0 --> Я 1 +1
2) q^ 1 --> q^ 1 +1 13) q1^ 1 --> Я 2 +1
3) q^ 2 --> q^ 2 +1 14) q1^ 2 --> Я 3 +1
4) q^ 3 --> q^ 3 +1 15) q1^ 3 --> Я 4 +1
5) q^ 4 --> q^ 4 +1 16) q1^ 4 --> Я 5 +1
6) q^ 5 --> q^ 5 +1 17) q1^ 5 --> Я 6 +1
7) q^ 6 --> q^ 6 +1 18) q1^ 6 --> Я 7 +1
8) q^ 7 --> q^ 7 +1 19) q1^ 7 --> Я 8 +1
9) q^ 8 --> q^ 8 +1 20) q1^ 8 --> Я 9 +1
10) q^ 9 --> q^ 9 +1 21) q1^ 9 --> q1^ 0 -1
11) q^ # --> q1^ # -1 22) q1^ # --> Я 1 0
Наведемо траєктрію T1^ роботи М1 при x = '349'. Тоді :
Стани траєктрії T1^ Номера команд П1
t[0] 2= 0 /#/q^ 349/#/ 4
t[1] 2= 0 /#/3 q^ 49/#/ 5
t[2] 2= 0 /#/34 q^ 9/#/ 10
t[3] 2= 0 /#/349 q^ #/#/ 11
t[4] 2= 0 /#/34 q1^ 9#/#/ 21
t[5] 2= 0 /#/3 q1^ 40#/#/ 16
t[6] 2= 0 /#/3 Я 50#/#/ кінцева
Значить, f1[М1]('349') = '350'
Самостійно побудуйте траєкторії машини Тюрінга М1 при
x = '9999', '0' i e = ''.
Завдання:
R R R
F6(W) =W W W W W
Текст прорами:
; @-a
; &-b
; %-c
(q0,a) (q0,a,+1)
(q0,b) (q0,b,+1)
(q0,c) (q0,c,+1)
(q0,#) (q1,!,-1)
(q1,a) (q2,@,+1)
(q1,b) (q3,&,+1)
(q1,c) (q4,%,+1)
(q2,a) (q2,a,+1)
(q2,b) (q2,b,+1)
(q2,c) (q2,c,+1)
(q2,&) (q2,&,+1)
(q2,@) (q2,@,+1)
(q2,%) (q2,%,+1)
(q2,!) (q2,!,+1)
(q2,#) (q5,@,-1)
(q3,a) (q3,a,+1)
(q3,b) (q3,b,+1)
(q3,c) (q3,c,+1)
(q3,&) (q3,&,+1)
(q3,@) (q3,@,+1)
(q3,%) (q3,%,+1)
(q3,!) (q3,!,+1)
(q3,#) (q5,&,-1)
(q4,a) (q4,a,+1)
(q4,b) (q4,b,+1)
(q4,c) (q4,c,+1)
(q4,&) (q4,&,+1)
(q4,@) (q4,@,+1)
(q4,%) (q4,%,+1)
(q4,!) (q4,!,+1)
(q4,#) (q5,%,-1)
(q5,a) (q1,a,0)
(q5,b) (q1,b,0)
(q5,c) (q1,c,0)
(q5,&) (q5,&,-1)
(q5,@) (q5,@,-1)
(q5,%) (q5,%,-1)
(q5,!) (q5,!,-1)
(q5,#) (q6,#,+1)
(q6,@) (q6,@,+1)
(q6,&) (q6,&,+1)
(q6,%) (q6,%,+1)
(q6,!) (q70,!,+1)
;(q6,#) (q7,!,0)
(q70,#) (q71,?,-1)
(q70,@) (q70,a,+1)
(q70,&) (q70,b,+1)
(q70,%) (q70,c,+1)
(q71,!) (q7,!,+1)
(q71,a) (q71,a,-1)
(q71,b) (q71,b,-1)
(q71,c) (q71,c,-1)
;++++++++++++++++++++++++++++++
;(q7,!) (q7,!,+1)
(q7,a) (q8,@,+1)
(q7,b) (q9,&,+1)
(q7,c) (q10,%,+1)
(q7,?) (q13,?,0)
(q8,a) (q8,a,+1)
(q8,b) (q8,b,+1)
(q8,c) (q8,c,+1)
(q8,&) (q8,&,+1)
(q8,@) (q8,@,+1)
(q8,%) (q8,%,+1)
(q8,!) (q8,!,+1)
(q8,?) (q8,?,+1)
(q8,#) (q12,a,-1)
(q9,a) (q9,a,+1)
(q9,b) (q9,b,+1)
(q9,c) (q9,c,+1)
(q9,&) (q9,&,+1)
(q9,@) (q9,@,+1)
(q9,%) (q9,%,+1)
(q9,!) (q9,!,+1)
(q9,?) (q9,?,+1)
(q9,#) (q12,b,-1)
(q10,a) (q10,a,+1)
(q10,b) (q10,b,+1)
(q10,c) (q10,c,+1)
(q10,&) (q10,&,+1)
(q10,@) (q10,@,+1)
(q10,%) (q10,%,+1)
(q10,!) (q10,!,+1)
(q10,?) (q10,?,+1)
(q10,#) (q12,c,-1)
(q12,!) (q12,!,-1)
(q12,?) (q12,?,-1)
(q12,a) (q12,a,-1)
(q12,b) (q12,b,-1)
(q12,c) (q12,c,-1)
(q12,@) (q7,@,+1)
(q12,&) (q7,&,+1)
(q12,%) (q7,%,+1)
(q12,#) (q13,#,+1)
(q13,a) (q13,a,+1)
(q13,b) (q13,b,+1)
(q13,c) (q13,c,+1)
(q13,@) (q13,a,+1)
(q13,&) (q13,b,+1)
(q13,%) (q13,c,+1)
(q13,?) (q13,?,+1)
(q13,!) (q13,!,+1)
(q13,#) (q14,^,-1)
;================================
(q14,?) (q15,?,+1)
(q14,a) (q14,a,-1)
(q14,b) (q14,b,-1)
(q14,c) (q14,c,-1)
(q15,a) (q16,@,+1)
(q15,b) (q17,&,+1)
(q15,c) (q18,%,+1)
(q15,^) (q20,^,+1)
(q16,a) (q16,a,+1)
(q16,b) (q16,b,+1)
(q16,c) (q16,c,+1)
(q16,&) (q16,&,+1)
(q16,@) (q16,@,+1)
(q16,^) (q16,^,+1)
(q16,%) (q16,%,+1)
(q16,!) (q16,!,+1)
(q16,?) (q16,?,+1)
(q16,#) (q19,a,-1)
(q17,a) (q17,a,+1)
(q17,b) (q17,b,+1)
(q17,c) (q17,c,+1)
(q17,&) (q17,&,+1)
(q17,@) (q17,@,+1)
(q17,%) (q17,%,+1)
(q17,!) (q17,!,+1)
(q17,^) (q17,^,+1)
(q17,?) (q17,?,+1)
(q17,#) (q19,b,-1)
(q18,a) (q18,a,+1)
(q18,b) (q18,b,+1)
(q18,c) (q18,c,+1)
(q18,&) (q18,&,+1)
(q18,@) (q18,@,+1)
(q18,%) (q18,%,+1)
(q18,!) (q18,!,+1)
(q18,?) (q18,?,+1)
(q18,^) (q18,^,+1)
(q18,#) (q19,c,-1)
(q19,!) (q19,!,-1)
(q19,^) (q19,^,-1)
(q19,?) (q19,?,-1)
(q19,a) (q19,a,-1)
(q19,b) (q19,b,-1)
(q19,c) (q19,c,-1)
(q19,@) (q15,@,+1)
(q19,&) (q15,&,+1)
(q19,%) (q15,%,+1)
(q19,#) (q20,#,+1)
(q20,a)(q20,a,+1)
(q20,b)(q20,b,+1)
(q20,c)(q20,c,+1)
(q20,#)(q21,!,-1)
(q21,a)(q22,@,+1)
(q21,b)(q23,&,+1)
(q21,c)(q24,%,+1)
(q21,!) (q21,!,-1)
(q21,^) (q21,^,-1)
(q21,?) (q21,?,-1)
(q21,@) (q21,@,+1)
(q21,&) (q21,&,+1)
(q21,%) (q21,%,+1)
(q21,#)(R,#,0)
(q22,a) (q22,a,+1)
(q22,b) (q22,b,+1)
(q22,c) (q22,c,+1)
(q22,&) (q22,&,+1)
(q22,@) (q22,@,+1)
(q22,%) (q22,%,+1)
(q22,!) (q22,!,+1)
(q22,#) (q25,@,-1)
(q23,a) (q23,a,+1)
(q23,b) (q23,b,+1)
(q23,c) (q23,c,+1)
(q23,&) (q23,&,+1)
(q23,@) (q23,@,+1)
(q23,%) (q23,%,+1)
(q23,!) (q23,!,+1)
(q23,#) (q25,&,-1)
(q24,a) (q24,a,+1)
(q24,b) (q24,b,+1)
(q24,c) (q24,c,+1)
(q24,&) (q24,&,+1)
(q24,@) (q24,@,+1)
(q24,%) (q24,%,+1)
(q24,!) (q24,!,+1)
(q24,#) (q25,%,-1)
(q25,a)(q21,a,0)
(q25,b)(q21,b,0)
(q25,c)(q21,c,0)
(q25,#)(q26,#,+1)
(q25,&) (q25,&,-1)
(q25,@) (q25,@,-1)
(q25,%) (q25,%,-1)
(q25,!) (q25,!,-1)
(q25,^) (q25,^,-1)
(q25,?) (q25,?,-1)
;++++++++++++++++++++++++++
(q26,@) (q26,a,+1)
(q26,&) (q26,b,+1)
(q26,%) (q26,c,+1)
(q26,?) (q26,.,+1)
(q26,^) (q26,.,+1)
(q26,!) (q26,.,+1)
(q26,#) (R,#,0)
Результати роботи програми:
Введіть стрічку даних: aaabcc
Результуюча стрічка: aaabcc.ccbaaa.ccbaaa.ccbaaa.aaabcc
Введіть стрічку даних: ababab
Результуюча стрічка: ababab.bababa.bababa.bababa.ababab
Введіть стрічку даних: a
Результуюча стрічка: a.a.a.a.a
Введіть стрічку даних: cccca
Результуюча стрічка: cccca.acccc.acccc.acccc.cccca
Завдання:
L1= { (a^n)(b^2n)(c^3n)(a^n) | n>=1}
Текст прорами:
(q0,b) (R,F,0)
(q0,c) (R,F,0)
(q0,a) (q1,$,+1)
(q0,#) (R,F,0)
(q1,b) (q22,@,+1)
(q1,c) (R,F,0)
(q1,a) (q1,a,+1)
(q1,#) (R,F,0)
(q1,@) (q1,@,+1)
(q22,b) (q2,@,+1)
(q22,c) (R,F,0)
(q22,a) (q22,a,+1)
(q22,#) (R,F,0)
(q22,@) (q22,@,+1)
(q2,b) (q2,b,+1)
(q2,c) (q3,@,+1)
(q2,a) (R,F,0)
(q2,#) (R,F,0)
(q2,@) (q2,@,+1)
(q3,b) (R,F,0)
(q3,c) (q4,@,+1)
(q3,a) (R,F,0)
(q3,#) (R,F,0)
(q4,b) (R,F,0)
(q4,c) (q5,@,+1)
(q4,a) (R,F,0)
(q4,#) (R,F,0)
(q5,b) (R,F,0)
(q5,c) (q5,c,+1)
(q5,a) (q6,@,-1)
(q5,#) (R,F,0)
(q5,@) (q5,@,+1)
(q6,@) (q6,@,-1)
(q6,b) (q6,b,-1)
(q6,c) (q6,c,-1)
(q6,a) (q6,a,-1)
(q6,$) (q7,$,+1)
(q7,a) (q1,$,+1)
(q7,@) (q8,@,+1)
(q8,@) (q8,@,+1)
(q8,b) (R,F,0)
(q8,c) (R,F,0)
(q8,a) (R,F,0)
(q8,#) (R,T,0)
Результати роботи програми:
Введўть стрўчку даних: abbccca
Результуюча стрўчка: $@@@@@@T
Введўть стрўчку даних: aac
Результуюча стрўчка: $aF
Введўть стрўчку даних: aaccc
Результуюча стрўчка: $aFcc
Введўть стрўчку даних: aaaaa
Результуюча стрўчка: $aaaaF
Висновок: під час виконання лабораторної роботи я вивчив емуляцiю на ПЕОМ машин Тюрінга і констроювання програм для них.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора