Описание программы, реализующей распознающий автомат

Вводная часть

Программа: машина Тьюринга

Обозначение программы: turing.exe

Программа используется для построения моделей машины Тьюринга

Функциональное назначение

Программа предназначена для моделирования работы машины Тьюринга. Программа обрабатывает цепочку входных символов согласно правилам грамматики, записанным в виде таблицы переходов, и устанавливает состояние, позволяющее определить допустимость цепочки.

Системные требования

1. Операционная система семейства Windows, Linuxили MacOSс графическим фреймворком Qtверсии не менее 4.0

.   Оперативная память не менее 32 мегабайт

.   10 мегабайт места на жестком диске

Описание входных данных

В настройках программы задается следующая информация:

.   Таблица переходов конечного автомата

.   Множество состояний машины

.   Множество входных символов

.   Пустой символ ленты

.   Конечные состояния машины

.   Допустимые состояния машины

На вход программе подается строка, символы которой входят в множество входных символов машины. Строка проверяется на корректность и вводит в программу только содержащиеся во входном множестве символы.

Для допуска строки вводится дополнительное состояние, не являющеся состоянием минимального автомата, но требуемое для окончания работы машины Тьюринга с допускающим результатом.

9. Описание контрольного примера

Назначение

Контрольный пример необходим для тестирования программной реализации автомата - программы «turing».

Исходные данные

Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата: {x0, x1, x2, x3, x4, x5, x6, x7}.

Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики. Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек. Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символS. Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал. Выписать терминальные символы из этого правила и если в конце стоит нетериманл, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.

Итак, получаем допускающие цепочки:

1) S ->x5x5x4B ->x4 - допустить

2 8

отсюда получаем цепочку: x5x5x4x4;

2) S ->x3C ->x7E ->x5-допустить

3 9 14

цепочка: x3 x7 x5;

3) S ->x1F ->x3x0x6 - допустить

4 17

цепочка: x1x3x0 x6;

Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле. Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.

Недопустимые цепочки:

4) x5 x5 x4

5) x3 x7

)   x1 x3 x0

Результаты испытания программы

Результаты испытания программы представлены в таблице 6.

 

Таблица 6. Результат испытания программы

Номер тестируемой цепочки	Входная цепочка	Результат работы программы
1	x5 x5 x4 x4	цепочка допущена
2	x3 x7 x5	цепочка допущена
3	x1 x3 x0 x6	цепочка допущена
6	x5 x5 x4	цепочка отвергнута
7	x3 x7	цепочка отвергнута
8	x1 x3 x0	цепочка отвергнута

 

Результаты испытания программы совпали с ожидаемыми, что говорит о правильности построения минимального автомата и реализации программы.

Заключение

 

В ходе данной работы было выполнено построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Автоматы, полученные двумя способами, идентичны, что говорит о правильности выполнения вычислений.

Для автоматизированной обработки входных последовательностей была реализована машина Тьюринга с устанавливаемым автоматом. Проверка теоретически построенных допустимых и недопустимых последовательностей показала, что программа работает верно.

 

Список литературы

 

1. Методические указания для самостоятельной работы студентов по дисциплине «Теория вычислительных процессов и структур». Ч1/ Ижевск. гос. техн. университет; Сост. Сенилов М.А. ИжГТУ, 2000.

2. ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М.: Издательство стандартов, 1980. - 2 с.