Машина Тьюринга

Автор: Пользователь скрыл имя, 21 Апреля 2013 в 09:41, курсовая работа

Описание работы

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, и недетерминированной в противном случае.
Цель – сформировать формальное определение и написать программную реализацию машины Тьюринга, распознающей язык L = {wÎ{0, 1}* │w не содержит 2-х идущих подряд нулей}
Результат – формальное определение, программная реализация машины Тьюринга, распознающей язык L = {wÎ{0, 1}* │w не содержит 2-х идущих подряд нулей}

Содержание

Ведение………………………………………………………………...4
ПОСТАНОВКА ЗАДАЧИ……………………………………….........6
ФОРМАЛЬНО ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА………..7
ПРОГРАММНАЯ МОДЕЛЬ МАШИНЫ ТЬЮРИНГА……….........8
ПРОТОКОЛЫ РАБОТЫ МАШИНЫ ТЬЮРИНГА……...................22
ВЫВОД………………………………………………………………..23
СПИСОК ЛИТЕРАТУРЫ…………………….………..………...... 25
Приложение А……………………………………………………....... 25
Приложение Б………………………………………………………....27
11.Экранные формы программы………………………… …………....27

Скачать полностью (91.55 Кб) Сколько стоит заказать работу?

Работа содержит 1 файл

курсовой ДС.doc

— 196.00 Кб (Скачать)

}

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="01000"/>

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

// Не содержит 2-х подряд нулей

1q1->1q1R

0q1->0q2R

1q2->1q1R

Bq1->BSTOP

Bq2->BSTOP

</textarea>

</td>

</tr>

</table>

<br>

</div>

</div>

<body>

</html>

</font>

4 ПРОТОКОЛЫ РАБОТЫ МАШИНЫ ТЬЮРИНГА

// Не содержит 2-х подряд нулей

1q1->1q1R

0q1->0q2R

1q2->1q1R

Bq1->BSTOP

Bq2->BSTOP

ВЫВОДЫ

Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

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

Информация о работе Машина Тьюринга