TRABAJO AUTOMATAS Y LENGUAS FORMALES1 2



TRABAJO AUTOMATAS Y LENGUAS FORMALES



PRESENTADO POR:
ADRIANA BELTRAN GOMEZ




PRESENTADO A:
CARLOS ALBERTO AMAYA







UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA ¨UNAD¨
CEAD GIRARDOT
Febrerode 2015


Problemas a desarrollar:
Dado el siguiente Autómata M Finito : M =(K, ∑, q0, δ, F) donde:
K = {q0, q1, q2, q3, q4, } ∑ = {a,b,c} q0 Es el estado Inicial F = q3, q4,
donde lafunción de transición está dada por:
 : {q0, q1, q2, q3, q4 } × {a,b,c} → {q0, q1, q2,
q3, q4 } → q0 → { q3 , q4, }
δ (q0, a ) = q1 δ (q0, ) = q2 δ (q1, b ) = q3 δ (q2 , a) = q4 δ (q3, a ) = q1 δ (q3, c ) = q2 δ (q4, b ) = q2
1. Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata dedar el concepto de determinismo)

f
a
b
c
λ
→
q0
q1
Ø
Ø
q2

q1
Ø
q3
Ø
Ø

q2
q4
Ø
Ø
Ø
#
q3
q1
Ø
q2
Ø
#
q4
Ø
q2
Ø
Ø

R1= EL tipo de autómata es AFND porque permite que las transiciones tengan comoetiqueta la palabra vacía. De hecho q0 es un AFND- λ , al que se le permite cambiar de un estado sin necesidad de leer un símbolo de entrada.
R2 = EL tipo de autómata es AFND porque para cada estado actualy una transición dada hay varios estados finales y/o vacíos.

2. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describircada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.




Una Tupla es una lista que no puede modificarse después de creada, aunque se define de la mismaforma que una lista, difiere de esta última porque el conjunto se encierra entre paréntesis en lugar de corchetes.
M= (K, Σ, q0, δ, F)
K es un conjunto de estados;
Σ es un alfabeto;
δ: K x Σ → K, δ:{q0, q1, q2, q3, q4 } × {a,b,c} → {q0, q1, q2, q3, q4 } → q0 → { q3 , q4, },  es una función de transición para un AFD;
q0 ϵ K es el estado inicial;
M C K es un conjunto de estados finales o de...