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

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

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

<html>

<head>

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

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 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>

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

</div>

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

</div>

</table>

</div>

<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()"/>

Скорость

<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>

<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>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</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>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

</td>

<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>

<br>

</div>

</div>

<body>

</html>

</font>

Наши рекомендации

Программирование машины Тьюринга

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

Понятие машины Тьюринга. Формальные грамматики.

Основные положения машины Тьюринга

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

Машины тьюринга (одноленточные детерминированные)

Теорема Гёделя и машины Тьюринга

Определение машины Тьюринга

Недетерминированные машины Тьюринга и NP-задачи

← Предыдущая страница | Следующая страница →