Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Формирование формального определения и написание программы, реализующей работу машины Тьюринга (Javascript)

Формирование формального определения и написание программы, реализующей работу машины Тьюринга (Javascript)

Изучение методик языка Javascript по формализации и решению поставленной задачи, технологических приемов разработки программ на языке Javascript, HTML, CSS. Формально определение машины Тьюринга, распознающую язык. Ее программная модель, протоколы работы.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 03.03.2015
Размер файла 220,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

КУРСОВОЙ ПРОЕКТ

по дисциплине «Дискретные структуры»

на тему:

Формирование формального определения и написание программы, реализующей работу машины Тьюринга (Javascript)

Целью данной курсовой работы является формирование формального определения и написание программы, реализующей работу машины Тьюринга. В рамках курсовой работы предусмотрено изучение методик языка Javascript по формализации и решению поставленной задачи, технологических приемов разработки программ на языке Javascript, HTML, CSS.

Результатом курсовой работы является html страница, которая демонстрирует работу поставленной задачи в полном объёме.

МАШИНА ТЬЮРИНГА, ВРЕМЕННАЯ СЛОЖНОСТЬ, АЛФАВИТ, ЛЕНТА, ЯЗЫК, РАСПОЗНАВАНИЕ, ПРОТОКОЛ, ПРИНАДЛЕЖНОСТЬ

Содержание

  • Введение
  • 1. Постановка задачи
  • 2. Формально определение машины Тьюринга
  • 3. Программная модель машины Тьюринга
  • 4. Протоколы работы машины Тьюринга
  • Вывод
  • Список литературы
  • Приложения

Введение

Алгоритм можно определить как точное предписание о выполнении каких-либо действий. Существует множество способов формального представления алгоритма. Например, машины Тьюринга, машины Поста, цепи Маркова. машина тьюринг программа язык

Машина Тьюринга в качестве формального представления алгоритма была предложена английским математиком Аланом Тьюрингом в 1937 году. Машина Тьюринга это простой точный объект, который может являться объектом математического исследования. Любой алгоритм (были выработаны различные определения алгоритмов и в итоге все они эквивалентны между собой) может быть реализован машиной Тьюринга.

Существует множество разновидностей машин Тьюринга: распознающие, считающие, с накапливающими состояниями и т.д. В общем говоря машина Тьюринга это совокупность шести объектов:

T=(K, , , , F, q0),

где K, , - конечные множества, множество состояния, входной алфавит (записываются слова подлежащие распознанию), ленточный алфавит.

F - конечное состояние головки машины Тьюринга.

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

1. Постановка задачи

Необходимо формально определить машину Тьюринга, распознающую язык

L = {w{0, 1}* w не содержит 3-х идущих подряд единиц}

Проверить правильность составления машины Тьюринга на протоколах.

Реализовать программную модель машины Тьюринга.

2. Формально определение машины Тьюринга

1q1->1q2R

1q2->1q3R

1q3->1q4

1q4->BSTOP

0q1->0q1R

0q2->0q2R

0q3->0q3R

Bq4->BSTOP

K - множество состояний;

K={q2, q3, }.

- входной алфавит; ={0, 1}.

Г - ленточный алфавит; Г = {0, 1}.

Q1 - начальное состояние.

В - пустое множество.

STOP- состояние полной остановки машины;

3. Программная модель машины Тьюринга

Содержание файла javascript.js

Файл содержит основные функции, реализующие работу программы.

<p style="line-height: 100%"><font size="6"><!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>

<head>

<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">

<title>Документ без названия</title>

<link href="style.css" rel="stylesheet" type="text/css">

<script type="text/javascript">

var ctlTape;

var ctlProgram;

var ctlErrorType;

var ctlErrorMessage;

var ctlConfig;

var ctlState;

var ctlNewState;

var ctlSpeed;

var ctlNextCommand;

var ctlTapeContainer;

var flTMDoStop = true;

// Поддержка алфавита

var chkDigitIds = "0 1 2 3 4 5 6 7 8 9";

var smbDigit = "0123456789";

var chkAlphaIds = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z";

var smbAlpha = "abcdefghijklmnopqrstuvwxyz";

var chkSymbolIds = "Less Greater Equal Plus Minus Star Slash Hat Percent";

var smbSymbol = "<>=+-*/^%";

var nExtraSymbolNumber = 14;

var smbNBSP;

// Поддержка множества состояний

var chkStateIds = "Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19";

var stState = ["q1", "q2", "q3", "q4", "q5", "q6", "q7", "q8", "q9",

q10", "q11", "q12", "q13", "q14", "q15", "q16", "q17", "q18", "q19"];

var cellWidth = 30;

var nExtraStateNumber = 10;

var arTMTape = [];

var tapeShift = 100;

var setTMProgram;

var setTMAlphabet;

var setTMStates;

var strTMCurrentState;

var idxTMCurrentCell;

function init() {

ctlTape = document.getElementById("tape");

ctlProgram = document.getElementById("program");

ctlErrorType = document.getElementById("errorType");

ctlErrorMessage = document.getElementById("errorMessage");

ctlConfig = document.getElementById("config");

ctlState = document.getElementById("state");

ctlNewState = document.getElementById("newState");

ctlSpeed = document.getElementById("speed");

ctlNextCommand = document.getElementById("ctlNextCommand");

ctlTapeContainer = document.getElementById("ctlTapeContainer");

smbNBSP = document.getElementById("ctlNBSP").firstChild.nodeValue;

for(var i = -tapeShift; i < tapeShift; i++) {

createCell(i);

}

tmClearTape();

}

function createCell(n) {

// var cell = document.createElement("div");

var cell = document.createElement("td");

var input = document.createElement("input");

input.setAttribute("type", "text");

input.setAttribute("size", 1);

cell.appendChild(input);

cell.setAttribute("tabindex", "1");

cell = ctlTape.appendChild(cell);

cell.firstChild.readOnly = true;

cell.tabIndex = 1;

cell.tapeIndex = n;

cell.onclick = function() { ctlTape_click(this.tapeIndex); };

// cell.setAttribute("style", "left: " + (30 * (n + tapeShift)) + "px");

return cell;

}

function tmFocusCell(n) {

if(!isNaN(idxTMCurrentCell)) {

var cell = ctlTape.childNodes[idxTMCurrentCell + tapeShift];

cell.className = cell.className.replace(/focused/, "")

.replace(/\s+/g, " ").replace(/^\s+/, "").replace(/\s+$/, "");

}

var cell = ctlTape.childNodes[n + tapeShift];

cell.className = "focused" + (cell.className ? " " + cell.className : "");

idxTMCurrentCell = n;

cell.firstChild.focus();

// if(ctlTapeContainer.doScroll) {

// var th = Math.floor(600 / (tapeShift*2) * (n + tapeShift));

// window.setTimeout(function() {

// while(th--)

// ctlTapeContainer.doScroll("scrollbarRight");

// }, 50);

// //alert(100 / (tapeShift*2) * (n + tapeShift));

// }

}

function tmSetCellValue(n, v) {

if(v == 'B')

v = '';

arTMTape[n + tapeShift] = v;

var cell = ctlTape.childNodes[n + tapeShift];

//while(cell.childNodes.length)

// cell.removeChild(cell.lastChild);

//var txt = document.createTextNode(v || smbNBSP);

//cell.appendChild(txt);

cell.className = cell.className.replace(/blankSymbol/, "")

.replace(/\s+/g, " ").replace(/^\s+/, "").replace(/\s+$/, "");

if(v == '')

cell.className = "blankSymbol" + (cell.className ? " " + cell.className: "");

cell.firstChild.value = v;

}

function tmGetCellValue(n) {

var v = arTMTape[n + tapeShift];

return v == '' ? 'B' : v;

}

function tmClearErrors() {

while(ctlErrorType.childNodes.length)

ctlErrorType.removeChild(ctlErrorType.lastChild);

while(ctlErrorMessage.childNodes.length)

ctlErrorMessage.removeChild(ctlErrorMessage.lastChild);

}

function tmCompileError(strType, b, e) {

if(ctlProgram.setSelectionRange && typeof(ctlProgram.setSelectionRange) == "function" && b <= e) {

ctlProgram.select();

ctlProgram.setSelectionRange(b, e);

}

tmClearErrors();

var errT = document.createTextNode(strType);

ctlErrorType.appendChild(errT);

var strMessage = ctlProgram.value.substring(b, e);

var errM = document.createTextNode(strMessage);

ctlErrorMessage.appendChild(errM);

alert(strType);

}

function tmCompile(text) {

tmClearErrors();

function nextE(bb) {

var ee = text.substring(bb, text.length).indexOf("\n");

return ee == -1 ? text.length : bb + ee;

}

var arNewProgram = {};

for(var idxLine = 1, b = 0, e = nextE(b); b < text.length; b = e + 1, e = nextE(b), idxLine++ ) {

var line = text.substring(b, e);

line = line.replace(/\/\/.*$/, "");

line = line + " ";

// var arMatch = line.match(/^\s*(?:([^\s][a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*\-\>[^\s][a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*[LRH]?)\s+)*$/);

var arMatch = line.match(/^\s*(?:([^\s][a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*\-\>[^\s][a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*[LRH]?)\s+)*$/);

if(!arMatch)

return tmCompileError("Синтаксическая ошибка в " + idxLine + "-й строке", b, e);

for(var idxCmd = 1; idxCmd < arMatch.length; idxCmd++) {

var strCmd = arMatch[idxCmd];

if(!strCmd)

continue;

var parsedCommand = tmParseCommand(strCmd, idxLine);

if(!parsedCommand)

return tmCompileError("Непредвиденная ошибка в " + idxLine + "-й строке", b, e);

if("errorMessage" in parsedCommand)

return tmCompileError(parsedCommand.errorMessage, b, e);

var prefix = "" + parsedCommand.smbFrom + parsedCommand.stFrom;

if(prefix in arNewProgram)

return tmCompileError("Строка " + idxLine + ": Повторение команды " + strCmd + " для символа '"

+ parsedCommand.smbFrom + "' и состояния " + parsedCommand.stFrom, b, e);

arNewProgram[prefix] = parsedCommand;

}

}

setTMProgram = arNewProgram;

return true;

}

function tmParseCommand(str, idxLine) {

// var arMatch = str.match(/(.)([a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*)\-\>(.)([a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*)([LRH]?)/);

var arMatch = str.match(/(.)([a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*)\-\>(.)([a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*)([LRH]?)/);

if(!arMatch || arMatch.length != 6)

return {

errorMessage: "Строка " + idxLine + ": Непредвиденная ошибка в команде " + str

};

var smbFrom = arMatch[1];

var stFrom = arMatch[2];

var smbTo = arMatch[3];

var stTo = arMatch[4];

var mvTo = arMatch[5];

if(!(smbFrom in setTMAlphabet))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " символ '" + smbFrom + "' не входит в алвфавит Вашей машины Тьюринга"

};

if(!(stFrom in setTMStates))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " состояние '" + stFrom + "' не входит в множество состояний Вашей машины Тьюринга"

};

if(!(smbTo in setTMAlphabet))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " символ '" + smbTo + "' не входит в алвфавит Вашей машины Тьюринга"

};

if(!(stTo in setTMStates))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " состояние '" + stTo + "' не входит в множество состояний Вашей машины Тьюринга"

};

if(!mvTo)

mvTo = 'H';

return {

smbFrom : smbFrom,

smbTo : smbTo,

stFrom : stFrom,

stTo : stTo,

mvTo : mvTo

};

}

function tmClearTape() {

for(var idxCell = -tapeShift; idxCell < tapeShift; idxCell++) {

tmSetCellValue(idxCell, "");

}

}

function tmSetConfig(strConfig) {

tmClearErrors();

for(var idxSymbol = 0; idxSymbol < strConfig.length; idxSymbol++)

if(!(strConfig.charAt(idxSymbol) in setTMAlphabet))

return tmCompileError("Символ '" + strConfig.charAt(idxSymbol) + "' не входит в алфавит Вашей машины Тьюринга");

tmClearTape();

for(var idxSymbol = 0; idxSymbol < strConfig.length; idxSymbol++)

tmSetCellValue(idxSymbol, strConfig.charAt(idxSymbol));

tmFocusCell(strConfig.length + 1);

tmFocusCell(0);

}

function tmSetState(strState) {

tmClearErrors();

if(!strState)

return tmCompileError("Неопределенное состояние машины Тьюринга");

if(!(strState in setTMStates))

return tmCompileError("Состояние '" + strState + "' не входит в множество состояний Вашей машины Тьюринга");

while(ctlState.childNodes.length)

ctlState.removeChild(ctlState.lastChild);

tnState = document.createTextNode(strState);

ctlState.appendChild(tnState);

strTMCurrentState = strState;

return true;

}

function tmStep() {

tmClearErrors();

if(strTMCurrentState == "STOP") {

alert("Работа машины Тьюринга успешно завершена");

return false;

}

if(!strTMCurrentState)

return tmCompileError("Не установлено состояние машины Тьюринга");

if(!(strTMCurrentState in setTMStates))

return tmCompileError("Состояние '" + strTMCurrentState + "' не входит в множество состояний Вашей машины Тьюринга");

if(isNaN(idxTMCurrentCell))

return tmCompileError("Не установлена текущая ячейка машины Тьюринга");

var smbCurrent = tmGetCellValue(idxTMCurrentCell);

if(!smbCurrent)

smbCurrent = 'B';

if(!(smbCurrent in setTMAlphabet))

return tmCompileError("Символ '" + smbCurrent + "' не входит в алфавит Вашей машины Тьюринга");

var prefix = "" + smbCurrent + strTMCurrentState;

if(!setTMProgram)

return tmCompileError("Нет ни одной команды для выполнения");

if(!(prefix in setTMProgram))

return tmCompileError("Нет команды для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

var cmd = setTMProgram[prefix];

if(!(cmd.smbTo in setTMAlphabet))

return tmCompileError("Символ '" + cmd.smbTo + "' не входит в алфавит Вашей машины Тьюринга\n" +

"При выполнении команды для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

if(!(cmd.stTo in setTMStates))

return tmCompileError("Состояние '" + cmd.stTo + "' не входит в множество состояний Вашей машины Тьюринга\n" +

"При выполнении команды для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

if(!(cmd.mvTo == 'L' || cmd.mvTo == 'R' || cmd.mvTo == 'H'))

return tmCompileError("Непредвиденная ошибка при выполнении перемещения в команде для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

tmSetCellValue(idxTMCurrentCell, cmd.smbTo);

tmSetState(cmd.stTo);

switch(cmd.mvTo) {

case 'L':

tmFocusCell(idxTMCurrentCell - 1);

break;

case 'R':

tmFocusCell(idxTMCurrentCell + 1);

break;

case 'H':

break;

default:

return tmCompileError("Непредвиденная ошибка при выполнении перемещения в команде для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

}

return true;

}

function tmStart() {

var ids = ["btnStep", "btnStart", "btnSetState", "btnSetConfig", "btnShowNextCommand"];

for(var i = 0; i < ids.length; i++)

document.getElementById(ids[i]).disabled = true;

document.getElementById("btnStop").disabled = false;

flTMDoStop = false;

tmShowNextCommand();

window.setTimeout(tmRepeatStep, ctlSpeed.value);

}

function tmRepeatStep() {

if(!flTMDoStop && tmStep()) {

tmShowNextCommand();

window.setTimeout(tmRepeatStep, ctlSpeed.value);

return;

}

document.getElementById("btnStop").disabled = true;

var ids = ["btnStep", "btnStart", "btnSetState", "btnSetConfig", "btnShowNextCommand"];

for(var i = ids.length; i--; )

document.getElementById(ids[i]).disabled = false;

}

function tmStop() {

flTMDoStop = true;

}

function tmSetAlphabet() {

tmClearErrors();

var alphabet = {};

alphabet['B'] = 'B';

var ids = (chkDigitIds + " " + chkAlphaIds + " " + chkSymbolIds).split(" ");

var smbs = (smbDigit + smbAlpha + smbSymbol);

for(var i = 0; i < ids.length; i++)

if(document.getElementById("symbol" + ids[i]).checked)

alphabet[smbs.charAt(i)] = smbs.charAt(i);

for(var i = 0; i < nExtraSymbolNumber; i++) {

var smb = document.getElementById("extraSymbol" + i).value;

if(!smb)

continue;

if(smb in alphabet)

return tmCompileError("Невозможно включить символ '" + smb +

"' в алфавит дважды");

if(smb.length != 1)

return tmCompileError("Невозможно включить в алфавит " + smb.length + "-буквенное слово '" + smb + "'");

alphabet[smb] = smb;

}

setTMAlphabet = alphabet;

return true;

}

function tmSetStates() {

tmClearErrors();

var states = {};

states['STOP'] = 'STOP';

var ids = chkStateIds.split(" ");

for(var i = 0; i < ids.length; i++)

if(document.getElementById("state" + ids[i]).checked)

states[stState[i]] = stState[i];

for(var i = 0; i < nExtraStateNumber; i++) {

var st = document.getElementById("extraState" + i).value;

if(!st)

continue;

if(st in states)

return tmCompileError("Невозможно включить состояние '" + st +

"' в множество состояний машины Тьюринга дважды");

// if(!st.match(/^[a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*$/))

if(!st.match(/^[a-zA-Z0-9][^\s\-\>]*$/))

return tmCompileError("Некорректное имя для состояния: '" + st + "'");

states[st] = st;

}

setTMStates = states;

return true;

}

function tmAddStateInput(trParent, tdBefore) {

var td = document.createElement("td");

var input = document.createElement("input");

input.setAttribute("type", "textbox");

input.setAttribute("id", "extraState" + nExtraStateNumber++);

input.setAttribute("class", "extraState");

td.appendChild(input);

if(tdBefore)

td = trParent.insertBefore(td, tdBefore);

else

td = trParent.appendChild(td);

td.firstChild.className = "extraState";

return td;

}

function tmMoreStates() {

var tdMoreStates = document.getElementById("tdMoreStates");

var parent = tdMoreStates.parentNode;

var colsNumber = Math.ceil(nExtraStateNumber / 10) + 4;

var percentWidth = Math.floor(100 / colsNumber);

for(var td = parent.firstChild; td != tdMoreStates; td = td.nextSibling)

if(td.nodeName.toLowerCase() == "td")

td.setAttribute("width", percentWidth + "%");

tdMoreStates.setAttribute("width", 100 - colsNumber * percentWidth + "%");

var tdStateInput = tmAddStateInput(parent, tdMoreStates);

tdStateInput.setAttribute("width", percentWidth + "%");

for(var tr = parent.nextSibling; tr; tr = tr.nextSibling)

if(tr.nodeName.toLowerCase() == "tr")

var td = tmAddStateInput(tr);

}

function tmShowNextCommand() {

tmClearNextCommand();

var prefix = "" + tmGetCellValue(idxTMCurrentCell) + strTMCurrentState;

if(!setTMProgram || !(prefix in setTMProgram))

return;

var cmd = setTMProgram[prefix];

var txt = prefix + "->" + cmd.smbTo + cmd.stTo + cmd.mvTo;

var tn = document.createTextNode(txt);

ctlNextCommand.appendChild(tn);

}

function tmClearNextCommand() {

while(ctlNextCommand.childNodes.length)

ctlNextCommand.removeChild(ctlNextCommand.lastChild);

}

function btnShowNextCommand_click() {

tmClearNextCommand();

var text = ctlProgram.value;

if(!(tmSetAlphabet() && tmSetStates()))

return;

if(!tmSetState(strTMCurrentState))

return;

if(tmCompile(text))

tmShowNextCommand();

}

function btnStep_click() {

tmClearNextCommand();

var text = ctlProgram.value;

if(!(tmSetAlphabet() && tmSetStates()))

return;

if(!tmSetState(strTMCurrentState))

return;

if(tmCompile(text) && tmStep())

tmShowNextCommand();

}

function btnStart_click() {

tmClearNextCommand();

var text = ctlProgram.value;

if(!(tmSetAlphabet() && tmSetStates()))

return;

if(!tmSetState(strTMCurrentState))

return;

if(tmCompile(text))

tmStart();

}

function btnStop_click() {

tmStop();

}

function btnSetConfig_click() {

tmClearNextCommand();

var strConfig = ctlConfig.value;

if(tmSetAlphabet() && tmSetConfig(strConfig))

tmShowNextCommand();

}

function btnSetState_click() {

tmClearNextCommand();

var strState = ctlNewState.value;

if(tmSetStates() && tmSetState(strState))

tmShowNextCommand();

}

function ctlTape_click(n) {

if(flTMDoStop) {

tmFocusCell(n);

tmShowNextCommand();

}

}

function chkAllDigit_click(checked) {

var ids = chkDigitIds.split(" ");

for(var i = 0; i < ids.length; i++)

document.getElementById("symbol" + ids[i]).checked = checked;

}

function chkAllAlpha_click(checked) {

var ids = chkAlphaIds.split(" ");

for(var i = 0; i < ids.length; i++)

document.getElementById("symbol" + ids[i]).checked = checked;

}

function chkAllSymbol_click(checked) {

var ids = chkSymbolIds.split(" ");

for(var i = 0; i < ids.length; i++)

document.getElementById("symbol" + ids[i]).checked = checked;

}

</script>

<body onload="init()">

<span id="ctlNBSP">&nbsp;</span>

<div class="next-command-container">

<h1> Следующая команда </h1>

<div id="ctlNextCommand"></div>

</div>

<div class="state-container">

<h1> Текущее состояние </h1>

<div id="state"></div>

</div>

<div id="ctlTapeContainer">

<table id="ctlTape">

<tr id="tape"></tr>

</table>

</div>

<div class="program-container">

<input type="button"

id="btnShowNextCommand"

value="Показать следующую команду"

onclick="btnShowNextCommand_click()"/>

<input type="button"

id="btnStep"

value="Шаг"

onclick="btnStep_click()"/>

<input type="button"

value="Старт"

id="btnStart"

onclick="btnStart_click()"/>

Скорость

<select id="speed">

<option value="0"/>Мгновенно

<option value="50"/>Очень быстро

<option value="200"/>Быстро

<option value="500" selected="true"/>Неспешно

<option value="1000"/>Медленно

<option value="5000"/>Очень медленно

</select>

<input type="button"

value="Стоп"

id="btnStop"

disabled="true"

onclick="btnStop_click()"/>

<table width="50%"

class="definitions"

cellpadding="4">

<tr>

<td width="50%">

<h2>Состояние</h2>

<input type="textbox"

id="newState"

value="q1"/><br/>

<input type="button"

value="Установить"

id="btnSetState"

onclick="btnSetState_click()"/>

</td>

<td colspan="2"

width="50%">

<h2>Конфигурация</h2>

<input type="textbox"

id="config"

value="10111"/>

<br/>

<input type="button"

value="Установить"

id="btnSetConfig"

onclick="btnSetConfig_click()"/>

</td>

<h2>Множество состояний</h2>

<table width="50%"

class="states">

<tr>

<td width="25%"><input type="checkbox"

checked="true" disabled="true"/>STOP</td>

<td width="25%"><input type="checkbox" id="stateQ10"/>q10</td>

<td width="25%"><input type="textbox" id="extraState0" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ1" checked="true"/>q1</td>

<td><input type="checkbox" id="stateQ11"/>q11</td>

<td><input type="textbox" id="extraState1" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ2" checked="true"/>q2</td>

<td><input type="checkbox" id="stateQ12"/>q12</td>

<td><input type="textbox" id="extraState2" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ3" checked="true"/>q3</td>

<td><input type="checkbox" id="stateQ13"/>q13</td>

<td><input type="textbox" id="extraState3" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ4"/>q4</td>

<td><input type="checkbox" id="stateQ14"/>q14</td>

<td><input type="textbox" id="extraState4" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ5"/>q5</td>

<td><input type="checkbox" id="stateQ15"/>q15</td>

<td><input type="textbox" id="extraState5" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ6"/>q6</td>

<td><input type="checkbox" id="stateQ16"/>q16</td>

<td><input type="textbox" id="extraState6" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ7"/>q7</td>

<td><input type="checkbox" id="stateQ17"/>q17</td>

<td><input type="textbox" id="extraState7" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ8"/>q8</td>

<td><input type="checkbox" id="stateQ18"/>q18</td>

<td><input type="textbox" id="extraState8" class="extraState"/></td>

</tr>

<tr>

<td><input type="checkbox" id="stateQ9"/>q9</td>

<td><input type="checkbox" id="stateQ19"/>q19</td>

<td><input type="textbox" id="extraState9" class="extraState"/></td>

</tr>

</table>

<h2>Алфавит</h2>

<table

width="50%"

class="alphabet">

<tr>

<td width="33%"

style="font-family: sans-serif;"

colspan="2">

<input type="checkbox"

id="allDigit"

onclick="chkAllDigit_click(this.checked)"/>

Цифры

</td>

<td width="33%"

style="font-family: sans-serif;"

colspan="2">

<input type="checkbox"

id="allAlpha"

onclick="chkAllAlpha_click(this.checked)"/>

Буквы

</td>

<td width="34%"

style="font-family: sans-serif;"

colspan="2">

<input type="checkbox"

id="allSymbol"

onclick="chkAllSymbol_click(this.checked)"/>

Символы

</td>

</tr>

<tr>

<td><input type="checkbox" id="symbol0" checked="true"/>0</td>

<td><input type="checkbox" id="symbolA"/>a</td>

<td><input type="checkbox" id="symbolK"/>k</td>

<td><input type="checkbox" id="symbolU"/>u</td>

<td><input type="checkbox" checked="true" disabled="true"/>B</td>

<td><input type="textbox" id="extraSymbol0"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol1" checked="true"/>1</td>

<td><input type="checkbox" id="symbolB"/>b</td>

<td><input type="checkbox" id="symbolL"/>l</td>

<td><input type="checkbox" id="symbolV"/>v</td>

<td><input type="checkbox" id="symbolLess"/>&lt;</td>

<td><input type="textbox" id="extraSymbol1"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol2"/>2</td>

<td><input type="checkbox" id="symbolC"/>c</td>

<td><input type="checkbox" id="symbolM"/>m</td>

<td><input type="checkbox" id="symbolW"/>w</td>

<td><input type="checkbox" id="symbolGreater"/>&gt;</td>

<td><input type="textbox" id="extraSymbol2"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol3"/>3</td>

<td><input type="checkbox" id="symbolD"/>d</td>

<td><input type="checkbox" id="symbolN"/>n</td>

<td><input type="checkbox" id="symbolX"/>x</td>

<td><input type="checkbox" id="symbolEqual"/>=</td>

<td><input type="textbox" id="extraSymbol3"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol4"/>4</td>

<td><input type="checkbox" id="symbolE"/>e</td>

<td><input type="checkbox" id="symbolO"/>o</td>

<td><input type="checkbox" id="symbolY"/>y</td>

<td><input type="checkbox" id="symbolPlus"/>+</td>

<td><input type="textbox" id="extraSymbol4"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol5"/>5</td>

<td><input type="checkbox" id="symbolF"/>f</td>

<td><input type="checkbox" id="symbolP"/>p</td>

<td><input type="checkbox" id="symbolZ"/>z</td>

<td><input type="checkbox" id="symbolMinus"/>-</td>

<td><input type="textbox" id="extraSymbol5"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol6"/>6</td>

<td><input type="checkbox" id="symbolG"/>g</td>

<td><input type="checkbox" id="symbolQ"/>q</td>

<td><input type="textbox" id="extraSymbol10"/></td>

<td><input type="checkbox" id="symbolStar"/>*</td>

<td><input type="textbox" id="extraSymbol6"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol7"/>7</td>

<td><input type="checkbox" id="symbolH"/>h</td>

<td><input type="checkbox" id="symbolR"/>r</td>

<td><input type="textbox" id="extraSymbol11"/></td>

<td><input type="checkbox" id="symbolSlash"/>/</td>

<td><input type="textbox" id="extraSymbol7"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol8"/>8</td>

<td><input type="checkbox" id="symbolI"/>i</td>

<td><input type="checkbox" id="symbolS"/>s</p></td>

<td><input type="textbox" id="extraSymbol12"/></td>

<td><input type="checkbox" id="symbolHat"/>^</td>

<td><input type="textbox" id="extraSymbol8"/></td>

</tr>

<tr>

<td><input type="checkbox" id="symbol9"/>9</td>

<td><input type="checkbox" id="symbolJ"/>j</td>

<td><input type="checkbox" id="symbolT"/>t</td>

<td><input type="textbox" id="extraSymbol13"/></td>

<td><input type="checkbox" id="symbolPercent"/>%</td>

<td><input type="textbox" id="extraSymbol9"/></td>

</tr>

</table>

</td>

<td width="50%">

<h2>Команды</h2>

<textarea

id="program"

wrap="off">

// Не содержит трех подряд единиц

1q1->1q2R

1q2->1q3R

1q3->1q4

1q4->BSTOP

0q1->0q1R

0q2->0q2R

0q3->0q3R

Bq4->BSTOP

</textarea>

</td>

</tr>

</table>

<div class="error-container">

<nobr id="errorType"></nobr>

<br>

<nobr id="errorMessage"></nobr>

</div>

<div class="copy">

&copy; Е.В Королёв , 2012;

</div>

</div>

<body>

</html>

</font>

4. Протоколы работы машины Тьюринга

// Не содержит трех подряд единиц

1q1->1q2R

1q2->1q3R

1q3->1q4

1q4->BSTOP

0q1->0q1R

0q2->0q2R

0q3->0q3R

Bq4->BSTOP

Вывод

Приобретены навыки составления машины Тьюринга, реализована машина Тьюринга программно с помощью функций Javascript и визуально оформлено с помощью HTML и CSS.

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

1. Баррет Д. JavaScript. Web-профессионалам. - Киев: БХВ - Киев, 2011.

2. Бранденбау Д. JavaScript: сборник рецептов. - СПб.: Питер, 2008.

3. Будилов В. JavaScript, XML и объектная модель документа. - СПб.: НиТ, 2011.

4. Вагнер Р. JavaScript. Энциклопедия пользователя (+CD-ROM). - Киев: ДиаСофт, 2009.

5. Вайк А. JavaScript в примерах. - Киев: ДиаСофт, 2008.

6. Вандер Вер Э. JavaScript для "чайников". - Диалектика, 2011.

7. Вейнер П. Языки программирования JAVA и JavaScript. - М: ЛОРИ, 2010.

8. Гарнаев А. Web-программирование на Java и JavaScript. - СПб.: БХВ Санкт-Перебург, 2008.

Приложение А

Техническое задание

1 Основание для разработки (основанием для разработки является задание на курсовую работу, выданное кафедрой прикладной математики и информатики).

2 Цель разработки (целью разработки является создание программной модели машины Тьюринга, распознающий заданный язык).

L = {w{0, 1}* w не содержит 3-х идущих подряд единиц}

3 Требования к программе:

- запрет ввода с клавиатуры символов не из входного алфавита заданного языка;

- ввод конфигурации

- установка состояния

  • вывод на экран каждого шага работы машины Тьюринга;
  • - вывод текущего состояния
  • - вывод следующего шага
  • 4 Требования к программной документации:
  • -пояснительная записка;
  • -руководство пользователя.

Приложение Б

Экранные формы программы

Рис.1 - Окно программы

Рис.2 - Окно команд

Рис.3 - Окно при завершении работы машины Тьюринга

Размещено на Allbest.ru

Подобные документы

  • Объектно-ориентированная система Animal

    Особенности исследования методик объектно-ориентированного проектирования программ с помощью языка UML по формализации, решению поставленной задачи, технологических приемов разработки объектно-ориентированных программ на языке Си++. Разработка программы.

    контрольная работа [188,9 K], добавлен 22.10.2014

  • Основные положения языка JavaScript

    Особенности составления программы (сценария) на языке JavaScript. Построение выражений из литералов, переменных, знаков операций, скобок. Элементы, используемые для хранения данных. Приоритет операций, порядок, в котором выполняются операции в выражении.

    лабораторная работа [40,2 K], добавлен 19.09.2019

  • Приемы программирования на JavaScript

    Изучение создания скриптов на JavaScript. Разработка программы выдачи простого предупреждения по событию Click при выборе гипертекстовой ссылки. Применение контейнера SCRIPT для размещение JavaScript-кода. Получение типа программы просмотра HTML-страниц.

    контрольная работа [21,1 K], добавлен 15.02.2010

  • Моделирование машины Тьюринга

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

    контрольная работа [82,4 K], добавлен 05.12.2010

  • Создание интерактивных Web-приложений с использованием языка программирования JavaScript

    Сравнительная характеристика, возможности и функции языков программирования JavaScript и PHP. Основные области их использования. Разработка интерактивного Web-приложения с применением JavaScript на примере теста по теме "Программирование на языке Delphi".

    курсовая работа [19,3 K], добавлен 01.07.2014

  • JavaScript

    Назначение и применение JavaScript, общие сведения. Понятие объектной модели применительно к JavaScript. Размещение кода на HTML-странице. URL-схема. Вставка (контейнер SCRIPT, принудительный вызов интерпретатора). Программирование свойств окна браузера.

    лекция [517,1 K], добавлен 09.03.2009

  • Создание интерактивных Web-приложений с использованием языка программирования JavaScript

    Исследование возможностей и областей использования языка программирования JavaScript. Сравнительный анализ языков программирования JavaScript и PHP. Разработка интерактивного Web-приложения на примере теста по теме "Программирование на языке Delphi".

    практическая работа [26,0 K], добавлен 04.02.2015

  • Технология написания клиентских приложений с использованием языка сценариев JavaScript

    Базовый синтаксис языка сценариев JavaScript. Создание страниц, включающих в себя программы, которые взаимодействуют с пользователем, управляют браузером и динамически создают HTML-содержимое. Работа с объектами, которые инкапсулируют данные и поведение.

    лабораторная работа [58,6 K], добавлен 25.05.2016

  • Встроенные Javascript функции

    Характеристика Javascript функции с параметрами (аргументами). Возврат значений, глобальные и локальные переменные в функции. Все способы создания пользовательских функций в Javascript. Область видимости переменных. Рекурсивная функция Javascript.

    лабораторная работа [75,8 K], добавлен 19.09.2019

  • Построение модели многоленточной машины Тьюринга для алфавита русского языка

    Методика разработки программы, предназначенной для разбора предложения с помощью многоленточной машины Тьюринга. Цели и назначение данной системы, основные требования, предъявляемые к ней. Организационно-исполнительные работы по содержанию системы.

    курсовая работа [386,8 K], добавлен 16.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены