Синтез распознающего автомата
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
8.1 Вводная часть
Программа: машина Тьюринга
Обозначение программы: turing.exe
Программа используется для построения моделей машины Тьюринга
8.2 Функциональное назначение
Программа предназначена для моделирования работы машины Тьюринга. Программа обрабатывает цепочку входных символов согласно правилам грамматики, записанным в виде таблицы переходов, и устанавливает состояние, позволяющее определить допустимость цепочки.
8.3 Системные требования
1.Операционная система семейства Windows, Linux или MacOS с графическим фреймворком Qt версии не менее 4.0
2.Оперативная память не менее 32 мегабайт
.10 мегабайт места на жестком диске
8.4 Описание входных данных
В настройках программы задается следующая информация:
1.Таблица переходов конечного автомата
2.Множество состояний машины
.Множество входных символов
.Пустой символ ленты
.Конечные состояния машины
.Допустимые состояния машины
На вход программе подается строка, символы которой входят в множество входных символов машины. Строка проверяется на корректность и вводит в программу только содержащиеся во входном множестве символы.
Для допуска строки вводится дополнительное состояние, не являющеся состоянием минимального автомата, но требуемое для окончания работы машины Тьюринга с допускающим результатом.
9. ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА
9.1 Назначение
Контрольный пример необходим для тестирования программной реализации автомата - программы turing.
9.2 Исходные данные
Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата
{x0, x1, x2, x3, x4, x5, x6, x7}
Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики.
Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек.
Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символ S.
Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал.
Выписать терминальные символы из этого правила и если в конце стоит нетериманл, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.
Итак, получаем допускающие цепочки:
1)S -> x5 x5 x4 B -> x4 - допустить
2 8
отсюда получаем цепочку: x5 x5 x4 x4;
2)S -> x3 C -> x7 E -> x5 - допустить
3 9 14
цепочка: x3 x7 x5;
3)S -> x1 F -> x3 x0 x6 - допустить
4 17
цепочка: x1 x3 x0 x6;
Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле.
Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.
Недопустимые цепочки:
4)x5 x5 x4
5)x3 x7
)x1 x3 x0
9.4 Результаты испытания программы
Результаты испытания программы представлены в таблице 6.
Таблица 6 Результат испытания программы
Номер тестируемой цепочкиВходная цепочкаРезультат работы программы1x5 x5 x4 x4цепочка допущена2x3 x7 x5цепочка допущена3x1 x3 x0 x6цепочка допущена6x5 x5 x4цепочка отвергнута7x3 x7цепочка отвергнута8x1 x3 x0цепочка отвергнута
Результаты испытания программы совпали с ожидаемыми, что говорит о правильности построения минимального автомата и реализации программы.
ЗАКЛЮЧЕНИЕ
В ходе данной работы было выполнено построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Автоматы, полученные двумя способами, идентичны, что говорит о правильности выполнения вычислений.
Для автоматизированной обработки входных последовательностей была реализована машина Тьюринга с устанавливаемым автоматом. Проверка теоретически построенных допустимых и недопустимых последовательностей показала, что программа работает верно.
Список литературы
- Методические указания для самостоятельной работы студентов по дисциплине "Теория вычислительных процессов и структур". Ч1/ Ижевск. гос. техн. университет; Сост. Сенилов М.А. ИжГТУ, 2000.
- ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М.: Издательство стандартов, 1980. - 2с.
ПРИЛОЖЕНИЕ 1
Текст программы
1.Заголосочный файл mainwindow.cpp
#ifndef MAINWINDOW_H
#define MAINWINDOW_H
#include
#include
#include
#include
Ui {MainWindow;
}
MainWindow : public QMainWindow
{_OBJECT
:MainWindow(QWidget *parent = 0);
~MainWindow();
:isStopState(const QChar c);isAllowedState(const QChar c);getMeaningByState(const QChar c);writeSymbol(QChar c);moveRight();moveLeft();::MainWindow *ui; ribbon;ribbonPos, fakePos;currentX, currentY;currentState;timer;running;ready;
slots:step();resetState();setRules();on_buttonSetStates_clicked();on_load_triggered();on_save_triggered();on_buttonSetString_clicked();
on_ruleTable_cellPressed(int row, int column);
on_comboWriteSymbol_currentIndexChanged(int index);
on_comboMoveTo_currentIndexChanged(int index);on_comboSetState_currentIndexChanged(int index);
on_comboSpaceSymbol_currentIndexChanged(int index);
on_buttonStep_clicked();
on_buttonStartStop_clicked();
on_horizontalSlider_sliderMoved(int position);
on_buttonReset_clicked();
on_lineEndState_