ТОП 10:

ОБРОБКА МАСИВІВ ТА СИМВОЛЬНИХ ДАНИХ



 

Мета роботи – обробка літерних символів та масивів.

 

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

 

1 Розробити МТ в алфавіті А = {0, 1}, яка б починала роботу з останньої одиниці масиву, що складається з декількох одиниць, зсувала його на одну клітинку вліво, залишаючи без змін решту вмісту стрічки. Головка зупиняється на першій одиниці перенесеного масиву.

2 Розробити МТ, яка б у вхідний ланцюжок, заданий в алфавіті нулем та одиницею, переставляла одиниці й нулі так, щоб усі одиниці були розташовані на початку, а нулі – на кінці ланцюжка.

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

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

5 Розробити МТ, яка б починала роботу з довільної клітинки та переміщуючись вправо, записувала підряд 2n нулів за заданого n>=1 і зупинялась на останньому з них.

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

7 Розробити МТ, яка б з n>=2 записаних на стрічці одиниць залишала на стічці n–2 одиниці, записані підряд.

8 Скласти функціональну схему МТ, яка б могла міняти місцями крайні літери з трьох записаних у довільному порядку літер: А, В, С. Каретка в стані q0 оглядає літеру, розташовану справа [12].

 

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

 

Алгоритми являють собою послідовність кроків, реалізованих строго описаною математичною моделлю машини з нескінченною пам’яттю.

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

Стан МТ може записуватися одним словом, записаним в алфавіті, яке є об’єднанням зовнішнього та внутрішнього алфавітів.

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

Нехай визначено деяке машинне слово W1. Тоді наступне машинне слово, яке отримується в результаті одного кроку роботи машини, можна позначити через W2, наступне через W3 і так далі. В результаті роботи МТ отримується наступна послідовність слів: W1, W2 Wn.

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

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

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

 

Приклад 1

Розробити МТ, яка б зменшувала в два рази масив, що складається з 2N елементів. Головка розташована на лівій клітинці.

1.1 Обрати вхідний алфавіт, який складається з символів: *|.

1.2 Представити МТ у вигляді таблиці відповідності (рис. 57).

1.3 Увести на інформаційну стрічку масив з парної кількості символів « | », наприклад 6 (рис. 57).

 

 

Рисунок 57 – МТ для обробки масиву символів « | »

 

1.4 Запустити програму для виконання.

Результат роботи програми наведено на рисунку 58.

1.5 Увести іншу послідовність симолів « | ». Проаналізувати роботу програми в даному випадку.

 

 

Рисунок 58 – Результат зменшення в два рази початкового масиву

 

Приклад 2

Розробити МТ, яка б з масиву, що складається з літер A та B, видаляла всі літери B, виконуючи також при цьому групування літер А.

Головка може бути розташованою як на лівій, так і на правій клітинках інформаційної стрічки.

2.1 Обрати вхідний алфавіт, що складається з літер А і B та символу *.

2.2 Представити МТ у вигляді таблиці відповідності (рис. 59).

 

 

Рисунок 59 – Уведення початкового масиву

 

Результат стискання довільного масиву наведено на рисунку 60.

 

Рисунок 60 – Результат стискання довільного масиву

 

2.3 Увести інший масив, проаналізувати отримані результати.

 

Приклад 3

Розробити МТ, яка б опрацьовувала слово з літер A і B таким чином, щоб зліва були розташовані літери A, а справа – літери B. Головка знаходиться на лівій літері.

3.1 Обрати вхідний алфавіт, який складається з літер та символів: A B * |.

3.2 Представити МТ у вигляді таблиці відповідності (рис. 61).

Рисунок 61 – Програма обробки слова з літер A і B

3.3 Увести слово з послідовності літер A і B, наприклад BBAABB.

Результат обробки слова BBAABB наведено на рисунку 62.

 

Рисунок 62 – Результат обробки введеного слова







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

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