Page 96 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 96
96
△/R △/R
X/X
X/R X/X
M2
Encuentra la primera X a la derecha de la cinta después de la celda actual.
Y/R Y/R
△/R △/R
Y/Y
X/R Y/Y
M3: encuentra la primera y a la derecha de la cinta, después de la celda actual.
Y/R X/R
Si se quiere construir una máquina de Turing que encuentre la segunda ocurrencia del símbolo
distinto de espacio en blanco que está a la derecha de la posición inicial de la cabeza, con bloques
de MT más simples, se tendría algo como esto:
