Turing automata készítés, hogyan?

jflap-et használtál már? turing automatát (meg másféle automatákat is) készíthetsz és tesztelhetsz vele, nagyon egyszerű használni.

én csináltam egy verziót, amiben miután végigfut egy szón és blank jelet olvas, mindig elfogadja a szót, közben pedig a hármasával álló nullákat lecseréli.

[link]

a kezdőállapotra gondolsz? ha egyest olvas, egyest ír és továbbmegy a következő karakterre, gyakorlatilag változatlanul hagyja az egyeseket, miközben áthalad rajtuk. az R pedig egy jobbra lépés, tehát a következő karakterhez lép.

például ha 111000 kerül beolvasásra, akkor háromszor történik meg az (1, 1, R) a q0 állapotban, aztán beolvas egy 0-át és átlép a q1 állapotba. ha a beolvasott szó a 0000, akkor egyszer sem hajtódik végre az (1, 1, R).

a lényeg az egészben, hogy a q1, q2, q3 állapotok számolják az egymás mellett álló nullákat. ha pl 1001...-et olvasol, akkor a q2 a negyedik karakternél visszalép a kezdőállapotba és elölről kezdi a nullák számlálását.

ha elérted a q3-at, az azt jelenti, hogy megvan a három 0 egymás mellett, elkezdheted átírni őket. a harmadik nullánál nem lép eggyel jobbra a fej, hanem helyben marad (S = stay). q4, q5, q6 állapotokba lépve írja át a három 0-át #-re hátulról kezdve. ha megérkezett q6-ba, akkor előre kell mennie újból, át a három # jelen, hogy továbbhaladjon a szón és az esetleges többi nullákat is megtalálja és átírja. ha ez megvolt, 2 lehetőség van: vagy 1-est olvas és visszakerül a kezdőállapotba, ahol a beolvasott 0-ák száma újra nulla, vagy ha nullát olvas, átmegy egyből q1-be, ami azt jelenti, hogy azt az egy 0-át már észlelte és megszámolta.

illetve még a harmadik lehetőség, hogy a szó véget ért. (pl. 11###010110011### )

a q7-et, ami a végső állapot, azért tettem bele, hogy legyenek szavak, amiket elfogad (annak nem látom sok értelmét, hogy átírja a 0-ákat, de sose ér célba az automata). nálam minden szót elfogad, ezért mutat minden állapotból egy nyíl q7-be.

ugye a turing automata szalagja úgy néz ki, hogy pl ... blank, blank, 1001110101001111 blank, blank ... (a blank jel az üres négyzet, a szó elején és végén van)

nálam tehát bárhol eléri a végén a blank jelet, elfogad. variálhatod, hogy csak akkor fogadjon el, ha talált három 0-át, de ahhoz több állapotra lesz szükséged.