История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2020-04-01 | 193 |
5.00
из
|
Заказать работу |
|
|
Вводная часть
Программа: машина Тьюринга
Обозначение программы: 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 с.
|
|
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!