Обробка масивів та символьних даних

 

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

 

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

 

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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

Нехай визначено деяке машинне слово W₁. Тоді наступне машинне слово, яке отримується в результаті одного кроку роботи машини, можна позначити через W₂, наступне – через W₃ і так далі. В результаті роботи МТ отримується наступна послідовність слів: W₁, W₂ … W_n.

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

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

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

 

Приклад 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 – Результат обробки введеного слова