Automatas Momento 1

DESARROLLO DE LA ACTIVIDAD TRABAJO COLABORATIVO N° 1

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 la funció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 de dar el concepto de determinismo)

Rta:

Tabla de transición



a

b

C

q0

q1

q2



q1



q3



q2

q4





q3

q1



q2

q4



q2



Diagrama de More

En VAS

En JLAP

El Tipo de autómata:

Es Autómata finito determinista (AFND)

El tipo de autómata es AFND porque desde el estado q0 tenemos dos posibles transiciones para el símbolo de entrada a, donde se considera que las dos transiciones son posibles, para este caso, pasar de q0 a q1 o pasar de q0 a q2, debido a que entre q1 a λ q2.

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

Rta:

El autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:

 es un conjunto finito de estados;

 es un alfabeto finito;

 es el estado inicial;

 es una función de transición;

 es un conjunto de estados finales o de aceptación.

Σ(

...