ТОП 10:

Основні прийоми роботи в програмі ALGO 2000



 

При представлення МТ у вигляді таблиці відповідності в клітинках розташовуються команди МТ. Формат команд МТ має наступний вигляд: aKq,

де

a – новий зміст поточної клітинки (новий символ зовнішнього алфавіту, який заноситься в поточну клітинку);

K – команда механізму протягування стрічки МТ («вліво», «вправо», «зупинитися»);Q – новий внутрішній стан МТ.Робота МТ полягає в тому, що каретка переміщується вздовж стрічки та друкує або стирає символи. Для того, щоб МТ почала працювати, необхідно задати зовнішній алфавіт, тобто вказати символи, які до нього входять, а також задати програму та деякий стан машини, тобто необхідно розташувати символи зовнішнього алфавіту на клітинах стрічки, зокрема можна всі клітини залишити пустими та поставити каретку навпроти однієї з клітинок. Робота машини на основі заданої програми здійснюється наступним чином. Припустимо, що МТ в даний момент часу перебуває у внутрішньому стані qi, а в клітинці, що оглядається, знаходиться символ aj. У результаті машина переходе до виконання команди aKq в клітинці, на перетині стовпчика qi та рядка aj:1) в поточну клітинку стрічки заносится новий символ a;2) виконується зсув каретки вліво або вправо, або ж зупинення роботи машини; 3) машина переходить в новий стан q.Для вводу команди в клітинку необхідно:1) ввести символ зовнішнього алфавіту;2) ввести одну з команд стрічкопротяжного механізму:· символ «<» означає переміщення каретки вліво;· символ «>» означає переміщення каретки вправо;· символ підкреслення «_» означає пробіл, тобто пусту клітинку;· символ знак оклику «!» означає зупинення програми (зображується в вигляді );3) ввести номер нового внутрішнього стану (вводиться тільки цифра, літера Q не вводиться).У випадку неправильного вводу команди в клітинці жодного запису не з’явиться. Для видалення або додавання стовпчиків чи рядків необхідно використовувати відповідні пункти головного меню або піктограми панелі інструментів. Запуск програми МТ починається зі стану q0.

ЛАБОРАТОРНА РОБОТА 1

РОЗВ’ЯЗАННЯ ПРОСТИХ ЗАДАЧ ЗА ДОПОМОГОЮ МТ З ВИКОРИСТАННЯМ ПРОГРАМНОГО ІНТЕРПРЕТАТОРА ALGO 2000

 

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

 

Завдання для виконання лабораторної роботи

 

1 Побудувати МТ, зовнішній алфавіт якої складається з символів «*»,«# », «&» таким чином, щоб уведені символи «# » та «&» перетворювались на символи «*» [9]. При цьому послідовність повина починатися з символів «*», а закінчуватися символами «&».

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

3 Побудувати МТ, яка починає роботу від довільної клітинки, що містить символ 1, переміщується вліво до тих пір, поки не пройде підряд п’ять символів 0. Головка повина зупинитися на першій клітинці зліва після п’яти символів 0, надрукувавши в цій клітинці символ 1. Вміст інших клітинок стрічки залишається незмінним.

4 Скласти функціональну схему МТ, яка зможе розташувати в порядку зростання цифри, введені в три клітинки інформаційної стрічки в довільному порядку. Каретка розташована на крайній лівій цифрі.

 

ЗАГАЛЬНІ ПОЛОЖЕННЯ

 

Будь–яка МТ пов'язана з двома кінцевими алфавітами: алфавітом вхідних символів A і алфавітом станів Q. Алфавіт А називається зовнішнім, а алфавіт Q – внутрішнім. З різними машинами Тьюрінга можуть бути пов'язані різні алфавіти A і Q.

Вхідне слово розміщується на стрічці – по одному символу в розташованих підряд клітинках. Ліворуч і праворуч від вхідного слова знаходяться тільки порожні клітинки. До алфавіту А завжди входить порожній символ «пробіл» – ознака того, що клітинка є порожньою.

Автомат може рухатися вздовж стрічки вліво або вправо, читати вміст клітинок і записувати в клітинки символи.

Робота МТ полягає в повторенні такого циклу дій, які є спільними для будь-якої МТ:

1) зчитування символу з клітинки, яку оглядає головка;

2) відшукування застосовуваної команди;

3) виконання відшуканої команди.

При цьому вважається, що в програмі не існує двох таких команд, перші два символи яких були б одинаковими.

МТ зупиняється в тому і тільки в тому випадку, коли жодна з команд її програми не є застосовуваною.

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

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

 







Последнее изменение этой страницы: 2017-02-08; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.90.86.231 (0.004 с.)