КУРСОВИЙ ПРОЕКТ
з дисципліни «Дискретні структури»
на тему:
Формування формального визначення і написання програми, що реалізує роботу машини Тьюринга (Javascript)
Метою даної курсової роботи є формування формального визначення і написання програми, що реалізує роботу машини Тьюринга. В рамках курсової роботи передбачено вивчення методик мови Javascript по формалізації і вирішення поставленого завдання, технологічних прийомів розробки програм на мові Javascript, HTML, CSS.
Результатом курсової роботи є html сторінка, яка демонструє роботу поставленого завдання в повному обсязі.
Машини Тюрінга, тимчасові складнощі, АЛФАВІТ, СТРІЧКА, МОВА, РОЗПІЗНАВАННЯ, ПРОТОКОЛ, ПРИПИСАНИМ
Зміст
Введення
1. Постановка завдання
2. Формально визначення машини Тьюринга
3. Програмна модель машини Тьюринга
4. Протоколи роботи машини Тьюринга
Висновок
Список літератури
Програми
Введення
Алгоритм можна визначити як точне розпорядження про виконання будь-яких дій. Існує безліч способів формального представлення алгоритму. Наприклад, машини Тьюринга, машини Посту, ланцюги Маркова. Машини Тюрінга програма мову
Машина Тьюринга в якості формального представлення алгоритму була запропонована англійським математиком Аланом Тьюрінгом в 1937 році. Машина Тьюринга це простий точний об'єкт, який може бути об'єктом математичного дослідження. Будь алгоритм (були вироблені різні визначення алгоритмів і в підсумку всі вони еквівалентні між собою) може бути реалізований машиною Тьюринга.
Існує безліч різновидів машин Тьюринга: розпізнають, які вважають, з накопичують станами і т.д. Загалом кажучи машина Тьюринга це сукупність шести об'єктів:
T=(K,?, G, d, F, q 0),
де K,? , G - кінцеві множини, безліч стану, вхідний алфавіт (записуються слова підлягають розпізнаванню), стрічковий алфавіт.
F - кінцевий стан головки машини Тьюринга.
Представлена ??курсова робота присвячена розпізнає машинам Тьюринга, як найбільш часто використовуваному класу машин Тьюринга.
1. Постановка завдання
Необхідно формально визначити машину Тьюринга, распознающую мову
={w? {0, 1} * и w не містить 3-х йдуть підряд одиниць}
Перевірити правильність складання машини Тьюринга на протоколах.
Реалізувати програмну модель машини Тьюринга.
2. Формально визначення машини Тьюринга
q1- gt; 1q2R
1q2- gt; 1q3R
q3- gt; 1q4
q4- gt; BSTOP
q1- gt; 0q1R
q2- gt; 0q2R
q3- gt; 0q3R- gt; BSTOP
K - безліч станів;
K={q 2, q 3,}.
S - вхідний алфавіт; S={0, 1}.
Г - стрічковий алфавіт; Г={0, 1}.
Q 1 - початковий стан.
В - порожня множина.
STOP- стан повної зупинки машини;
3. Програмна модель машини Тьюринга
Зміст файлу javascript.js
Файл містить основні функції, що реалізують роботу програми.
lt; p style= line-height: 100% gt; lt; font size= 6 gt; lt;! DOCTYPE HTML PUBLIC -//W3C //DTD HTML 4.01 Transitional//EN # justify" gt; lt; html gt;
lt; head gt;
lt; meta http-equiv= Content-Type content= text/html; charset=windows - 1251 gt;
lt; title gt; Документ без назви lt;/title gt;
lt; link href= style.css rel= stylesheet type= text/css gt;
lt; script type=laquo;text/javascriptraquo;gt;ctlTape;ctlProgram;ctlErrorType;ctlErrorMessage;ctlConfig;ctlState;ctlNewState;ctlSpeed;ctlNextCommand;ctlTapeContainer;flTMDoStop =True;
//Підтримка алфавітаchkDigitIds= 0 1 2 3 4 5 6 7 8 9 raquo ;; smbDigit= 0123456789 raquo ;; chkAlphaIds= ABCDEFGHIJKLMNOPQRSTU VWXY Z raquo ;;...
