Ejemplo polindrome, maquina de turing
1)
name: Binary palindrome
init: q0
accept: qAccept
q0,0
qRight0,_,>
qRight0,0
qRight0,0,>
qRight0,1
qRight0,1,>
q0,1
qRight1,_,>
qRight1,0
qRight1,0,>
qRight1,1
qRight1,1,>
qRight0,_
qSearch0L,_,<
qSearch0L,0
q1,_,<
qRight1,_
qSearch1L,_,<
qSearch1L,1
q1,_,<
q1,0
qLeft0,_,<
qLeft0,0
qLeft0,0,<
qLeft0,1
qLeft0,1,<
q1,1
qLeft1,_,<
qLeft1,0
qLeft1,0,<
qLeft1,1
qLeft1,1,<
qLeft0,_
qSearch0R,_,>
qSearch0R,0
q0,_,>
qLeft1,_
qSearch1R,_,>
qSearch1R,1
q0,_,>
qSearch0R,1
qReject,1,-
qSearch1R,0
qReject,0,-
qSearch0L,1
qReject,1,-
qSearch1L,0
qReject,0,-
q0,_
qAccept,_,-
q1,_
qAccept,_,-
qSearch0L,_
qAccept,_,-
qSearch0R,_
qAccept,_,-
qSearch1L,_
qAccept,_,-
qSearch1R,_
qAccept,_,-
2)
qLeft1,_
qSearch1R,_,>
qSearch1R,1
q0,_,>
qSearch0R,1
qReject,1,-
qSearch1R,0
qReject,0,-
qSearch0L,1
qReject,1,-
qSearch1L,0
qReject,0,-
q0,_
qAccept,_,-
q1,_
qAccept,_,-
qSearch0L,_
qAccept,_,-
qSearch0R,_
qAccept,_,-
qSearch1L,_
qAccept,_,-
qSearch1R,_
qAccept,_,-
3)
qLeft1,_
qSearch1R,_,>
qSearch1R,1
q0,_,>
qSearch0R,1
qReject,1,-
qSearch1R,0
qReject,0,-
qSearch0L,1
qReject,1,-
qSearch1L,0
qReject,0,-
q0,_
qAccept,_,-
q1,_
qAccept,_,-
qSearch0L,_
qAccept,_,-
qSearch0R,_
qAccept,_,-
qSearch1L,_
qAccept,_,-
qSearch1R,_
qAccept,_,-
4) Binario a decimal
name: Decimal to binary
init: qinit
accept: qfin
qinit,0
qinit,0,>
qinit,1
qinit,1,>
qinit,2
qinit,2,>
setrest1,_
continue,1,<
// continue
continue,0
continue,0,<
continue,1
continue,1,<
continue,_
continue2,_,<
// delimiter
continue2,_
halve,0,<
5) Decimal a binario
// Add 0.5 to the right
addHalf,0
jump,5,<
addHalf,1
jump,6,<
addHalf,2
jump,7,<
addHalf,3
jump,8,<
addHalf,4
jump,9,<
// Jump back
jump,0
halve,0,<
jump,1
halve,1,<
jump,2
halve,2,<
jump,3
halve,3,<
jump,4
halve,4,<
// If we halved successfully, we first remove the zero if there is one and then we go back
halve,_
removezero,_,>
removezero,0
removezero,_,>
removezero,1
goBack,1,>
removezero,2
goBack,2,>
removezero,3
goBack,3,>
removezero,4
goBack,4,>
removezero,5
goBack,5,>
removezero,6
goBack,6,>
removezero,7
goBack,7,>
removezero,8
goBack,8,>
removezero,9
goBack,9,>
// qfinished
removezero,_
qfin,_,>
// normal goBack
goBack,0
goBack,0,>
goBack,1
goBack,1,>
goBack,2
goBack,2,>
goBack,3
goBack,3,>
goBack,4
goBack,4,>
goBack,5
goBack,5,>
goBack,6
goBack,6,>
goBack,7
goBack,7,>
goBack,8
goBack,8,>
goBack,9
goBack,9,>
// rest
goBack,_
rest,_,<
rest,0
rest0,_,>
rest0,_
setrest0,_,>
rest,5
rest1,_,>
rest1,_
setrest1,_,>
setrest0,0
setrest0,0,>
setrest0,1
setrest0,1,>
setrest1,0
setrest1,0,>
setrest1,1
setrest1,1,>
setrest0,_
continue,0,<
setrest1,_
continue,1,<
// continue
continue,0
continue,0,<
continue,1
continue,1,<
continue,_
continue2,_,<
// delimiter
continue2,_
halve,0,<
6)
// ------- States -----------|
// q0 - mod3 == 0 |
// q1 - mod3 == 1 |
// q2 - mod3 == 2 |
// qaccept - accepting state |
//---------------------------|
name: Binary numbers divisible by 3
init: q0
accept: qAccept
q0,0
q0,0,>
q0,1
q1,1,>
removing_the_markers,o
removing_the_markers,0,>
removing_the_markers,i
removing_the_markers,1,>
removing_the_markers,0
removing_the_markers,0,<
removing_the_markers,1
removing_the_markers,1,<
removing_the_markers,_
qfin,_,>
Comentarios
Publicar un comentario