Matematické Fórum

spider · 12. 04. 2009 14:45 — Editoval spider (12. 04. 2009 16:02)

Zdravim zdejsi osazenstvo. Chtel bych poprosit o pomoc s resenim nasledujiciho prikladu:
Popiste algoritmus ktery jako vstup dostane Turinguv stroj $M = (Q,\Sigma,\Gamma,\delta,q_0,F)$ a ktery jako vystup vyda deterministicky konecny automat prijimajici jazyk slov nad abecedou $(Q \cup \Gamma) \times (Q \cup \Gamma)$ takovych, ze dane slovo popisuje dve po sobe jdouci konfigurace Turingova stroje $M$ , tj. takovou dvojici konfiguraci $C_1, C_2$ , ze $M$ muze prejit z $C_1$ do $C_2$ jednim krokem. Kofigurace $C_1, C_2$ jsou ve slove zapsany pod sebou, ve dvou stopach.
Napriklad:
$a b b a a a b q_5 a a b a b b a$
$a b b a a a q_8 b a b a b b a$
V horni stope je zapsana konfigurace $C_1$ , kde ridici jednotka je ve stavu $q_5$ , na pasce je zapsano slovo $abbaaabaababba$ a hlava se nachazi na osme bunce pasky (pokud cislujeme od 1), obdobne pro konfiguraci $C_2$ ktera je v dolni stope.

Budu vdecny za jakoukoliv radu ci "nakopnuti", nejak vubec nevim co s tim. Predem dekuju za jakoukoliv pomoc.
edit: pokud jsem to dobre pochopil, tak v tom kartezskem soucinu, tedy ty jednotlive konfigurace budou jenom dvojice znaku, ovsem konfigurace muze byt dlouha v podstate jakkoliv pokud je konecne dlouha. Coz podle me znamena, ze nelze zachytit konfiguraci, kdy je hlava uprostred pasky.

Kondr · 12. 04. 2009 23:27

Taková páska má vlastně tři části
1) část neznámé délky, na které jsou obě konfigurace shodné
2) část délky 2 nebo 3, na které se pásky liší
3) část neznámé délky, na které jsou obě konfigurace shodné

Jen konečně mnoho prostředních částí odpovídá korektní práci turingova stroje. Pokud stroj po přečtení znaku a ve stavu q1 má přejít do q2, zapsat b a pohnout hlavou doprava, je korektní druhou částí
q1a
bq1
pokud má být pohyb hlavy doleva, je korektní druhou částí
xq1a
q1xb
pro každý znak x.
Vygenerujeme tedy množinu všech korektních druhých částí a sestavíme automat M1, který takovou konečnou množinu slov přijímá.

Ten upravíme tak, že v z jeho vstupního stavu S přidáme přechody do S jakýmkoliv znakem tvaru (x,x) -- to odpovídá načítání první části. Stejnou úpravu proedeme v přijímajících stavech -- to odpovídá načítání třetí části.

spider · 15. 04. 2009 15:15

Dekuji za radu, moc mi to pomohlo.

Matematické Fórum

#1 12. 04. 2009 14:45 — Editoval spider (12. 04. 2009 16:02)

Prevod turingova stroje na konecny automat

#2 12. 04. 2009 23:27

Re: Prevod turingova stroje na konecny automat

#3 15. 04. 2009 15:15

Re: Prevod turingova stroje na konecny automat

Zápatí