Automatas

CONSTRUCCIÓN MODULAR DE MÁQUINAS DE TURING

Pasos para la construcción de una máquina de Turing:

a) Elimine las características de inicio de los estados iniciales de las maquinas, exceptola de aquel donde iniciara la maquina compuesta.

b) Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos seencuentre en ninguno de los diagramas que se combinan.
c) Para cada uno de los antiguos estados de parada p y cada x en y.

Los diagramas compuestos para la construcción modular de una máquina deTuring son aquellos en los que cada uno de los bloques de construcción se representa como un nodo, con flechas entre dichos nodos para indicar las transiciones entre bloques.

Se puede combinar dosmáquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. El contenido de la cinta cuando comienza la ejecución de la segunda máquina deTuring, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de l/e de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primeraBLOQUES DE CONSTRUCCION BASICOS






2. Diseñe una MT que reconozca {0^(n ) 1^n: n ≥ 1 }

Inicialmente, la cinta de entrada de M contendrá 0n 1n seguido de un número infinito de blancos.Repetidamente, M reemplaza el 0 más ala izquierda por X , mueve hacia la derecha la cabeza de la cinta hasta encontrar el 1 que esté más a la izquierda, reemplazándolo por Y , luego se mueve a laizquierda para encontrar la X más a la derecha, entonces mueve la cabeza una celda hacia la derecha y si
Encuentra un 0 entonces repite el ciclo. Sin embargo, si cuando se busca un 1, M encuentra unblanco en su lugar, entonces M se para sin aceptar su entrada. Si, después de cambiar un 1 por una Y, M no encuentra más 0’s, entonces M examina que no haya más 1, si no los hay entonces acepta su...