AUTOMATAS Y LENGUAJES FORMALESMOMENTO 2SANDRA TATIANA MEJIA FLOREZCODIGO: 1026267855DANIEL EDUARDO RAMREZ MARTNEZ

CODIGO: 1075236034

GRUPO: 14

TUTOR: CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

ECBTI

CCAV NEIVA

2014

Desarrollo de la actividadPARTE 1: Calcular el autmata mnimo correspondiente al siguiente autmata finito.

1. Enuncie el autmata en notacin matemtica = (,,,0,), = {0,1,2,3,4,5,6,7}, = {0,1} 0 = e

= {5}=es el e 2. Identifique los componentes del autmata (que tipo de tupla es) Conjunto de estados ={0,1,2,3,4,5,6,7} Alfabeto = {0,1} : Q x Q Funcin de transicin para un AFD 0 = e y = {3,5}=e el e 3. Identifique la tabla de transicin correspondiente 01

q0 q2 q1

q1 q4 q5

q2 q3 q4

# q3 q2 q7

q4 q7 q6

# q5 q6 q1

q6 q3 q4

q7 q4 q5

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas vlidas que terminen en el estado halt

011101

0101

101000

00011100011010

10010110

5. Encuentre la expresin regular vlida.

(01(1+1)0+0(0+0)+01(0+0)1+10(1+1)0+10(0+0)1+1(1+1)00+0(0+0)11+1(1+1))6. Encuentre su gramtica que sea vlida para la funcin de transicin (describa sus componentes y como se escriben matemticamente). Justifquela si la convierte a la Izquierda o a la derecha. Plsmela en el simulador y recrela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

Definimos o caracterizamos una gramtica regular como: Un cudruplo (V, , R, S) en donde:

V = Es el alfabeto de variables (,,,,,,,)

= Es el alfabeto de constantes {0,1}

R = Es el conjunto de reglas, es un subconjunto finito de ( )

S= Es el smbolo inicial y es un elemento de V

Esta gramtica, tiene las producciones por la derecha, es decir que es:

Lineal por la derecha, Cuando todas las producciones tienen la forma A aB o bien A a

Para nuestro caso:

A 1E

E 1A

=(,,R,S)

=[{,,,,,,,},{0,1},{1,1,1,0,1,1,1,1,0,0,,0,0,0,0,0,1,,0}]

Gramtica ordenada

7. Realice el rbol de Derivacin de esa gramtica. Cadena valida 1100

8. Identifique si ese rbol o gramtica es ambigua o no y plasme las razones de su afirmacin

La gramtica del rbol no es ambigua, ya que es univoca y es una gramtica libre de contexto que tiene asociado a un solo rbol de derivacin para toda la cadena del lenguaje.

9. Si el rbol de transicin es demasiado grande, a su criterio seleccione una regla en la que se detenga por cualquier rama (izquierda o derecha) y plsmelo hasta ah. (Es decir seleccione una cadena vlida para este tem).

A continuacin relaciono la regla para detener el rbol de transicin por la derecha

ReglaDerivacinArbol

S 1A

A 1E

E 0F

F 0C

C S1A

11E

110F

1100C

1100

ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR O YA MINIMIZADO: 1. Explicar el proceso de Minimizacin (que estados se suprimen y porque) Se visualizan estados equivalentes como q2 y q6, tambin q1 y q7, entonces los estados q2 y q6 envan al estado q3 el 0 y envan al estado q4 el 1, de igual manera los estados q1 y q7 envian al estado q4 el 0 y al estado q5 el 1.

2. Que transiciones se reemplazan o resultan equivalentes. Los estados que son equivalentes para el ejercicio son: q2 equivale a q6 y q1 equivale a q7.

3. Escribir la funcin de transicin del nuevo autmata. La nueva funcin de transicin es: {q0, q1, q2, q3, q4} x 0,1 { q0, q1, q2, q3, q4} q0{q3}4. Identificar la expresin regular (explicarla en la lectura matemtica que se le debe hacer).

5. Compruebe una cadena vlida para esa expresin regular.

6. Identificar el lenguaje que reconoce y cinco posibles cadenas vlidas

7. Identificar su gramtica. Demustrela para una cadena vlida del autmata.

8. Compare la gramtica con el autmata antes de minimizar (ya sea por la izquierda o derecha).

9. El autmatas nuevo expresarlo o graficarlo con su respectivo diagrama de Moore.

10. Identificar sus tablas de Transicin (plasmarlas) 01

q0q2q1

q1q4q3

q2q3q4

q3q2q1

#q4q1q2