AUTÓMATAS - MOMENTO 3 - EJERCICIO 1

AUTÓMATAS Y LENGUAJES FORMALES

PROBLEMA A DESARROLLAR: EJERCICIO 1

PRIMER EJERCICIO: DISEÑO DE UNA MT COMO TRANSDUCTOR

La máquina de Turing se puede comportar como transductor: Un transductor computa una determinada función sobre una cadena en lugar de computarla sobre un conjunto de enteros o de símbolos independientes.
Construyen una respuesta específica (una salida) para un problema planteado. Modifica el contenido de la cinta realizando cierta función.

Ejemplos:
 Calcula el complemento A1y el complemento A2
 Cuenta el número de símbolos de una palabra
 Divide una palabra en dos
 Desplaza símbolos en la cadena a izquierda y derecha
 Calcula la paridad de las cadenas
 Sustitución de dígitos
 Adición de bits bajo condiciones específicas matemáticas) 

Son muchísimas las aplicaciones que como “transducción puede generar una Máquina de Turing”

Ejemplo: La siguiente máquinas de Turing se puede comportar como transductor cuando reconoce cualquier combinación de ceros y unos, (también reconoce λ ); pero que tiene como salida el inverso de los símbolos que han entrado (cambia “0”s por “1”s y “1”s por “0”s). Observe que en este caso el mismo alfabeto se usa tanto para las cadenas de entrada como para la cinta. 

Actividades a desarrollar:

Diseñe Una MT que se comporte como transductor que reconozca el lenguaje L ={01u11*} (NO incluye o NO acepta la cadena  λ). 

La transducción (salida) debe ser que por cada símbolo que entre duplique el símbolo del alfabeto de la cinta, para el alfabeto 0 la cinta será a y para el alfabeto 1 el valor en la cinta será b: Ejemplo: para la cadena (11) la salida será (aaaa), para la cadena 01 la salida será: (aabb) El alfabeto de la cinta es debe ser diferente al alfabeto de entrada. Es decir el alfabeto de entrada es “0”  y el de la cinta “a”, y para la entrada “1” el de la cinta “b” con sus respectivos símbolos blanco si es que los necesita en su diseño

1. Identifique los componentes de la Máquina de Turing (descríbala).

2. Diséñela en un Diagrama de Moore.

3. Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada.

4. Identifique una cadena que no sea válida y justifíquela porque.

5. Ejecute el RunTest a una cadena aceptada que tenga la menos cinco símbolos 

6. Identifique en que momento la máquina se detiene.

7. Lo que acaba de diseñar es una MUT o una MT. Justifique su respuesta. 

[ PASO A PASO ]