8. Reconocimiento de cadenas de una MT

Para explicar el proceso de reconocimiento de cadenas se emplea la gráfica a continuación. La siguiente máquina de Turing acepta el lenguaje de palabras sobre {0,1} que comienzan y acaban con el mismo símbolo. Para validar este lenguaje, se presentan dos cadenas, una que cumple la condición y otra que será rechazada por la máquina. Se muestra entonces la cadena del lenguaje descrito, aceptada: 0110100 (Estado de aceptación q5).

Las transiciones, y el proceso seguido en la evaluación y aceptación de una cadena dada, se resumen en la siguiente tabla:

2. Cadena del lenguaje descrito, rechazada: 110

Para más información, se puede consultar el siguiente Ejemplo del reconocimiento de cadenas