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

Завданням є розробка машини Тьюринга, що розпізнає мову , її програмна реалізація.

3.1 Побудова алгоритму МТ

Машина Тьюринга в алфавіті має 19 станів. Система команд МТ з поясненнями приведені в таблиці 3.1.

Таблиця 3.1 - Система команд МТ

	Перевірка чи є першим символ a	Первинна перевірка того, що вихідне слово належить алфавіту
	Перевірка серії символів
	Перевірка серії символів
	Перевірка серії символів
	Видалення всіх символів, йдучи вліво
	Перехід вліво до кінця

Продовження таблиці 3.1

	Видалення всіх символів, йдучи вправо
	Видалення по черзі символу c та символу b (b замінюється на x)	Обчислення предикату
	Видалення по черзі символу b та символу a	Останнє обчислення предикату

3.2 Розробка програми-емулятора

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

Екранні форми програми наведені у додатку Г. Код програми наведений у додатку Б.

Алгоритм основної функції «work», яка відповідає за емуляцію роботи МТ можна побачити на рисунку 3.1.

поки CurrState≠FinalState.Text и stop≠true виконувати якщо n>0 и TrackBar.Position>0 то затримка(TrackBar.Position) інакше якщо n=-1 то stop:=істина finded:=хибність i:=1 поки i<StringGrid.RowCount-1 виконувати якщо непусто StringGrid.Cells[0,i] і непусто StringGrid.Cells[2,i] і непустоStringGrid.Cells[4,i] то якщо CurrState=StringGrid.Cells[0,i] і Tape.Cells[CurrPos,0]=StringGrid.Cells[1,i] то Tape.Cells[CurrPos,0]:=StringGrid.Cells[3,i] якщо StringGrid.Cells[4,i]='l' або StringGrid.Cells[4,i]='L' то CurrPos=CurrPos-1 інакше якщо StringGrid.Cells[4,i]='r' або StringGrid.Cells[4,i]='R' то CurrPos=CurrPos+1 CurrState:=StringGrid.Cells[2,i] finded:=істина вийти з циклу i:=i+1;

Рисунок 3.1 – Алгоритм роботи функції «work»

3.3 Тестові приклади. Перевірка працездатності програми

Протокол роботи програми для різних вхідних слів розглянемо в якості тестових прикладів.

Тестовий приклад для початкової конфігурації приведений у таблиці 3.2.

Таблиця 3.2 – Приклад розпізнавання слова машиною Тьюринга

Стан	Слово
	λabbcλ
	λabbcλ
	λabbcλ
	λabbcλ
	λabbcλ
	λabbcλ
	λabbλλ
	λabbλλ
	λabbλλ
	λabbλλ
	λaxbλλ
	λaxbλλ
	λaxbλλ
	λaxλλλ
	λaxλλλ
	λaxλλλ
	λaxλλλ
	λλxλλλ
	λλxλλλ
	λλxλλλ
	λλλλλλ
	λλλλλλ
	λλ1λλλ

Слово належить алфавіту, тому що кількість літер b відрізняється від кількості літер a та c. Програма-емулятор МТ працює правильно.

Тестовий приклад для початкової конфігурації приведений у таблиці 3.3.

Таблиця 3.3 – Приклад розпізнавання слова машиною Тьюринга

Стан	Слово
	λabcλ
	λabcλ
	λabcλ
	λabcλ
	λabcλ

Продовження таблиці 3.3

	λabλλ
	λabλλ
	λabλλ
	λaxλλ
	λaxλλ
	λaλλλ
	λλλλλ
	0λλλλ

Слово не належить алфавіту, тому що кількість літер b співпадає з кількістю літер a та c. Програма-емулятор МТ працює правильно.

Тестовий приклад для початкової конфігурації приведений у таблиці 3.4.

Таблиця 3.4 – Приклад розпізнавання слова машиною Тьюринга

Стан	Слово
	λccbbλ
	λλcbbλ
	λλλbbλ
	λλλλbλ
	λλλλλλ
	λλλλλ0

Слово не належить алфавіту, адже воно не містить жодної літери a. Програма-емулятор МТ працює правильно.

3.4 Часова складність алгоритму

Функція часової складності алгоритму має вигляд

Експериментальний та аналітичний графіки складності наведені у ДОДАТКУ Г.