AUTÓMATAS - EJERCICIO 1

AUTÓMATAS Y LENGUAJES FORMALES

PRIMER EJERCICIO: DISEÑO DE UNA MT COMO TRANSDUCTOR
 
Actividades a desarrollar:

Diseñe Una MT que se comporte como transductor que reconozca el lenguaje L ={01}* (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).

[ PASO A PASO ]
 
2. Diséñela en un Diagrama de Moore.

[ PASO A PASO ]
 
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.
[ PASO A PASO ]
 
 
4. Identifique una cadena que no sea válida y justifíquela porque.

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

[ PASO A PASO ]
 
6. Identifique en que momento la máquina se detiene.

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