TRABAJO COLABORATIVO

MOMENTO 2

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

ESCUELA DE CIENCIAS BASICAS, TECNOLOGIA E INGENIERIA

CEAD JOS ACEVEDO Y GMEZ

AUTOMATAS Y LENGUAJES FORMALES

SANDRA TATIANA MEJIA FLREZ- Cd. 1026267855

DANIEL EDUARDO RAMREZ MARTNEZ- Cd. 1075236034

Diciembre

2014

DESARROLLO DE LA ACTIVIDAD

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 =

= {5}=

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 =

= {3,5}=

3. Identifique la tabla de transicin correspondiente

0 1

q0 q2 q1 q1 q4 q5 q2 q3 q4

# q3 q2 q7 q4 q7 q6

# q5 q6 q1 q6 q3 q4 q7 q4 q5

Cada fila la corresponde a un estado q Q

El estado inicial se precede del smbolo

Cada estado final se precede del smbolo #

Cada columna corresponde a un smbolo de entrada x

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. 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.

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

derecha

Regla Derivacin rbol

S 1A

A 1E

E 0F

F 0C

C

S

1A

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 envan 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).

0 1

q0 q2 q1

q1 q4 q3

q2 q3 q4

q3 q2 q1

#q4 q1 q2