Rešitev: Turingov stroj Sodo število v dvojiškem zapisu

Iz MaFiRaWiki

Naloga: Turingov stroj Sodo število v dvojiškem zapisu

Clear[TS1, turingovStroj, d1, q0, q1, qs, qz]
TS1 = turingovStroj[{q0, q1, qs, qz}, {"0", "1"}, {"0", "1", "$"}, "$", d1, q0, qs, qz];

d1[q0, "1"] = {q0, "1", 1};
d1[q0, "0"] = {q0, "0", 1};
d1[q0, "$"] = {q1, "$", -1};
d1[q1, "1"] = {qz, "1", 0};
d1[q1, "0"] = {qs, "0", 0};
d1[q1, "$"] = {qz, "$", 0};

Preverimo delovanje Turingovega stroja:

Clear[prazenZnak,prehodnaFunkcija,zacetnoStanje,sprejemnoStanje,zavrnitvenoStanje]
prazenZnak[s_turingovStroj]:=s[[4]];
prehodnaFunkcija[s_turingovStroj]:=s[[5]];
zacetnoStanje[s_turingovStroj]:=s[[6]];
sprejemnoStanje[s_turingovStroj]:=s[[7]];
zavrnitvenoStanje[s_turingovStroj]:=s[[8]];

Clear[sprejema,novTrak]
sprejema[s_turingovStroj,w_]:=sprejema[s,zacetnoStanje[s],w];
sprejema[s_turingovStroj,qt_,""]:=sprejema[s, qt, {"",prazenZnak[s],""}];
sprejema[s_turingovStroj,qt_,w_String]:=sprejema[s, qt, {"",StringTake[w,1],StringDrop[w,1]}];
sprejema[s_turingovStroj, qt_, {t1_,tt_,t2_}]/;sprejemnoStanje[s]==qt := {True, {t1,tt,t2}};
sprejema[s_turingovStroj, qt_, {t1_,tt_,t2_}]/;zavrnitvenoStanje[s]==qt := {False, {t1,tt,t2}};
sprejema[s_turingovStroj, qt_, {t1_,tt_,t2_}]:=sprejema[s, First[prehodnaFunkcija[s][qt,tt]], novTrak[s,prehodnaFunkcija[s]
   [qt,tt],t1,t2]]
sprejema::usage="Funkcija sprejema[s,q,b] vrne True, če stroj s, ki je v stanju q, sprejema besedo b in False sicer.";

novTrak[s_turingovStroj, {_,nz_,0}, t1_, t2_]:={t1,nz,t2};
novTrak[s_turingovStroj, {_,nz_,1}, t1_, ""]:={StringJoin[t1,nz], prazenZnak[s], ""};
novTrak[s_turingovStroj, {_,nz_,1}, t1_, t2_]:={StringJoin[t1,nz], StringTake[t2,1], StringDrop[t2,1]};
novTrak[s_turingovStroj, {_,nz_,-1}, "", t2_]:={"", prazenZnak[s], StringJoin[nz,t2]};
novTrak[s_turingovStroj, {_,nz_,-1}, t1_, t2_]:={StringDrop[t1,-1], StringTake[t1,-1], StringJoin[nz,t2]};
novTrak::usage="Funkcija novTrak[s,p,lt,dt] vrne trak po prehodu glave stroja s, ki je predstavljen s trojico {levi del traku, 
   trenutni znak pod glavo, desni del traku}, če stroj s, naredi prehod p in je levo od glave na traku zapisano lt ter desno 
   od glave na traku zapisano dt.";

sprejeteBesede[s_turingovStroj, j_List] := (#[[2]] &) /@ Select[
      Map[{sprejema[s, #], #} &, j], #[[1, 1]] == True &];
zavrnjeneBesede[s_turingovStroj, j_List] := (#[[2]] &) /@ Select[Map[{
        sprejema[s, #], #} &, j], #[[1, 1]] == False &];

Primer:

Clear[jezik]
jezik = vse[{"0", "1"}, 3]
{, 0, 1, 00, 10, 01, 11, 000, 100, 010, 110, 001, 101, 011, 111}

sprejeteBesede[TS1, jezik]
{0, 00, 10, 000, 100, 010, 110}

zavrnjeneBesede[TS1, jezik]
{, 1, 01, 11, 001, 101, 011, 111}

Glej tudi

Osebna orodja