Page 113 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

113

Puede usar cualquier carácter para <símbolo actual> y <nuevo símbolo>, o '_' para representar
un espacio en blanco (espacio). Los símbolos distinguen entre mayúsculas y minúsculas.
<Dirección> debe ser 'l', 'r' o '*', que denota 'mover hacia la izquierda', 'mover hacia la derecha'
o 'no mover', respectivamente.
Cualquier cosa después de un ';' Es un comentario y es ignorado.
La máquina se detiene cuando alcanza cualquier estado que comienza con 'alto', por ejemplo.
Detener, detener-aceptar.

También:

'*' se puede usar como comodín en <símbolo actual> o <estado actual> para que coincida con
cualquier carácter o estado.
'*' se puede usar en <nuevo símbolo> o <nuevo estado> para significar 'sin cambio'.
'!' se puede usar al final de una línea para establecer un punto de interrupción, por ejemplo, '1
a b r 2!'. La máquina se detendrá automáticamente después de ejecutar esta línea.
Puede especificar la posición inicial de la cabeza usando '*' en la entrada inicial.

Ejemplo 1:

Este ejemplo de programa checa si un número es palíndromo.
; Input: a string of 0's and 1's, eg '1001001'

; Machine starts in state 0.

; State 0: read the leftmost symbol
0 0 _ r 1o
0 1 _ r 1i
0 _ _ * accept ; Empty input

; State 1o, 1i: find the rightmost symbol
1o _ _ l 2o
1o * * r 1o

1i _ _ l 2i
1i * * r 1i

; State 2o, 2i: check if the rightmost symbol matches the most recently read left-hand symbol
2o 0 _ l 3
2o _ _ * accept
2o * * * reject

2i 1 _ l 3
2i _ _ * accept
2i * * * reject

; State 3, 4: return to left end of remaining input
3 _ _ * accept
3 * * l 4
4 * * l 4
4 _ _ r 0 ; Back to the beginning

accept * : r accept2
accept2 * ) * halt-accept

reject _ : r reject2
reject * _ l reject
reject2 * ( * halt-reject

Initial input: 1001001 -> aceptado en 38 pasos 
Initial input: 0101001 -> rechazado en 17 pasos 