Automatas

AUTOMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO 4

YURANI GUERRERO DE GALINDO

UNIVERCIDAD NACIONAL ABIERTA Y A DISTANCIA

UNAD

FACULTAD DE CIENCIAS BACICAS E INGENIERIAINGENMIERIA DE SISTEMAS 2012

2. Diseñe una MT que reconozca {01: n ≥ 1 } n

• Cambie un 0 por una x (explique qué pasa con la máquina). Al cambiar el 0 por la X la maquina no reconoce ningúnvalor para trabajar • Cambie un 1 por una y (explique qué pasa con la máquina). Al cambiar el 1 por la y la maquina no reconoce ningún valor para trabajar vuelve a trabajar normamente con x y y comocuando estaba con 1 y 0 respectivamente • Identifique en qué momento la máquina de Turing se detiene. La condición nos indica que: n ≥ 1 solo lee un 0 en esl estado inicial al leer otro numero0 el proceso finaliza • Calcule la función δ • Grafíquela e identifique sus elementos. • Identifique la función de transición.

3. Construya una MT que acepte el Lenguaje (represéntela L ={abc: i ≥ 0} sobre Σ = {a,b,c} iii

Se cambia la a por una x moviéndose a la derecha. (explique qué pasa con la máquina). La maquina sigue si funcionamiento normal de estados como si no ubierahabido cambios xa (no afecta) • Luego se mueve a la izquierda pasando por encima de las bs (bes) (explique qué pasa con la máquina). Hace un cambio des estado al (bes) aue se encuentra en elestado q1 del grafico pasa al estado Q2 • Identifique en qué momento la máquina de Turing se detiene. No tiene un estado final por lo tanto el proceso nunca se detentra a no ser que exista un erroren el lenguaje q se introduzca • Calcule la función δ • Grafíquela e identifique sus elementos.

10. Considere la máquina de Turing de la figura e indique que tipo de cadenas decide ellenguaje que acepta.

Ejecute el RunTest a la cadena aceptada (muéstrela en la captura de imagen para el trabajo)

• Plasme el diagrama de Moore.

• Identifique la función de transición....