КУРСОВОЙ ПРОЕКТ
по дисциплине «Дискретные структуры»
на тему:
__________________________________________________________
(наименование темы)
Проект разработал студент
__________________________
Группы
_______________________
Руководитель проекта
__________________________
Оценка________________
2012г.
РЕФЕРАТ
Пояснительная записка курсовой работы:
24 страниц, 3 рисунка, 0 таблиц.
Целью данной курсовой работы является формирование формального определения и написание программы, реализующей работу машины Тьюринга. В рамках курсовой работы предусмотрено изучение методик языка Javascript по формализации и решению поставленной задачи, технологических приемов разработки программ на языке Javascript, HTML, CSS.
Результатом курсовой работы является html страница, которая демонстрирует работу поставленной задачи в полном объёме.
МАШИНА ТЬЮРИНГА, ВРЕМЕННАЯ СЛОЖНОСТЬ, АЛФАВИТ, ЛЕНТА, ЯЗЫК, РАСПОЗНАВАНИЕ, ПРОТОКОЛ, ПРИНАДЛЕЖНОСТЬ
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………………..4
2.ПОСТАНОВКА ЗАДАЧИ………………………………………............5
3.ФОРМАЛЬНО ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА………......6
4.ПРОГРАММНАЯ МОДЕЛЬ МАШИНЫ ТЬЮРИНГА………............7
5.ПРОТОКОЛЫ РАБОТЫ МАШИНЫ ТЬЮРИНГА……......................20
ВЫВОД…………………………………………………………………… 21
СПИСОК ЛИТЕРАТУРЫ……………………………………………….. 22
Приложение А……………………………………………………..............23
Техническое задание……………………………………………………....23
Приложение Б……………………………………………………………...24
Экранные формы программы……………………………… …………….24
ВВЕДЕНИЕ
Алгоритм можно определить как точное предписание о выполнении каких–либо действий. Существует множество способов формального представления алгоритма. Например, машины Тьюринга, машины Поста, цепи Маркова.
Машина Тьюринга в качестве формального представления алгоритма была предложена английским математиком Аланом Тьюрингом в 1937 году. Машина Тьюринга это простой точный объект который может являться объектом математического исследования. Любой алгоритм (были выработаны различные определения алгоритмов и в итоге все они эквивалентны между собой) может быть реализован машиной Тьюринга.
Существует множество разновидностей машин Тьюринга: распознающие, считающие, с накапливающими состояниями и т.д. В общем говоря машина Тьюринга это совокупность шести объектов: T=(K, å, G, d, F, q0), где K, å, G - конечные множества, множество состояния, входной алфавит (записываются слова подлежащие распознанию), ленточный алфавит. F – конечное состояние головки машины Тьюринга.
Представленная курсовая работа посвящена распознающим машинам Тьюринга, как наиболее часто используемому классу машин Тьюринга.
ПОСТАНОВКА ЗАДАЧИ
Необходимо формально определить машину Тьюринга, распознающую язык
L = {wÎ{0, 1}* │w не содержит 3-х идущих подряд единиц}
Проверить правильность составления машины Тьюринга на протоколах. Реализовать программную модель машины Тьюринга.
ФОРМАЛЬНО ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА
1q1->1q2R
1q2->1q3R
1q3->1q4
1q4->BSTOP
0q1->0q1R
0q2->0q2R
0q3->0q3R
Bq4->BSTOP
K – множество состояний;
K={q2, q3, }.
S – входной алфавит; S={0, 1}.
Г – ленточный алфавит; Г = {0, 1}.
Q1 – начальное состояние.
В – пустое множество.
STOP- состояние полной остановки машины;
