Maquina Turing simulando Autómata Determinista
Publicado por Pablo (3 intervenciones) el 07/08/2007 17:59:15
Hola, a ver si alguien puede echarme una mano con el siguiente ejercicio:
Se desea diseñar una Maquina de Turing (MT) capaz de simular el comportamiento de un Automata Finito Determinista (AFD) con alfabeto de entrada binario = {0; 1}. Para ello, debera existir en
la cinta de entrada de la MT un espacio reservado para la entrada del AFD, y a la derecha de dicha entrada se introducira un 1 si la palabra es aceptada y un 0 si no lo es.
Se pide:
Definir la codificacion, en terminos de cinta de una Maquina de Turing, del AFD y su entrada.
"Quería consultar si puede ser esta una buena definición:
palabraentrada$estadoactual#estadoEntradaestado#estadoEntradaestado...
Ejemplo: 1000$001#0010100#0011010...
La palabra de entrada es 1000
El estado actual es el 001(el estado 1)
0010100 (q1,0--->q4)
0011010. (q1,1---->q2)
"
Describir el comportamiento de dicha MT. Para ello especi car el numero de estados necesarios, y el comportamiento de cada uno de los estados. No es necesario incluir la tabla de transiciones
Poner un ejemplo de funcionamiento, indicando el resultado de la cinta para dicho ejemplo, en los pasos que se considere necesario. No hace falta indicar todos los pasos de ejecucion. Para
este ejemplo se debe elegir un AFD, incluyendo su tabla de transicion, e indicando como ser a la codifcacion de nida, para este ejemplo concreto
Se desea diseñar una Maquina de Turing (MT) capaz de simular el comportamiento de un Automata Finito Determinista (AFD) con alfabeto de entrada binario = {0; 1}. Para ello, debera existir en
la cinta de entrada de la MT un espacio reservado para la entrada del AFD, y a la derecha de dicha entrada se introducira un 1 si la palabra es aceptada y un 0 si no lo es.
Se pide:
Definir la codificacion, en terminos de cinta de una Maquina de Turing, del AFD y su entrada.
"Quería consultar si puede ser esta una buena definición:
palabraentrada$estadoactual#estadoEntradaestado#estadoEntradaestado...
Ejemplo: 1000$001#0010100#0011010...
La palabra de entrada es 1000
El estado actual es el 001(el estado 1)
0010100 (q1,0--->q4)
0011010. (q1,1---->q2)
"
Describir el comportamiento de dicha MT. Para ello especi car el numero de estados necesarios, y el comportamiento de cada uno de los estados. No es necesario incluir la tabla de transiciones
Poner un ejemplo de funcionamiento, indicando el resultado de la cinta para dicho ejemplo, en los pasos que se considere necesario. No hace falta indicar todos los pasos de ejecucion. Para
este ejemplo se debe elegir un AFD, incluyendo su tabla de transicion, e indicando como ser a la codifcacion de nida, para este ejemplo concreto
Valora esta pregunta
0