AUTMATAS Y LENGUAJES FORMALES

MOMENTO 2

PRESENTADO POR:

YOHANA ANDREA SCARPETTA

COD: 1081512316

Yas-2187@hotmail.com

ZONA: Sur

CEAD: NEIVA

YESICA YULIE SALGADO

COD: 1.079.181.739

yxik29@hotmail.com

ZONA: Sur

CEAD: NEIVA

EDWIN BENAVIDES edwinb32_8@hotmail.com

ZONA: Sur

CEAD: Mariquita

PRESENTADO A:

CARLOS ALBERTO AMAYA TARAZONA

TUTOR

logsei@hotmail.com

CIUDAD: DUITAMA

GRUPO: 32

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

2015

Descripcin general del trabajo

El siguiente trabajo corresponde al desarrollo del trabajo colaborativo del curso de

Autmatas y lenguajes formales, en el aplicaremos los contenidos temticos que

hemos adquirido del estudio de la unidad dos.

Los lenguajes independientes del contexto que tambin se conocen con el nombre

de gramticas de contexto libre son un mtodo recursivo sencillo de especificacin

de reglas gramaticales con las que se pueden generar cadenas de un lenguaje

Es factible producir de esta manera todos los lenguajes regulares, adems de que

existen ejemplos sencillos de gramticas de contexto libre que generan lenguajes

no regulares. Las reglas gramaticales de este tipo permiten que la sintaxis tenga

variedad y refinamientos mayores que los realizados con lenguajes regulares, en

gran medida sirven para especificarla sintaxis de lenguajes de alto nivel y otros

lenguajes formales

Problemas a desarrollar:

PARTE 1: Calcular el autmata mnimo correspondiente al siguiente

autmata finito

1. Enuncie el autmata en notacin matemtica

Dado el siguiente Autmata M Finito: M =(K, , q , , F) donde:

K = {q0, q1, q2, q3, q4, q5} = {0,1,2} q Es el estado Inicial F = q0,q1,q4,q5

donde la funcin de transicin est dada por: : {q0, q1, q2, q3, q4,q5 } {0,1,2} {q0,

q1, q2, q3, q4, q5} q { q0,q1,q4,q5}

2. Identifique los componentes del autmata (que tipo de tupla es)

Este ejercicio propuesto corresponde a una quntupla porque tiene 5 elementos:

Elementos de la tupla M = (K, , q , , F)

K = {q0, q1, q2, q3, q4, q5} representa un conjunto de estado.

= {0,1,2} corresponde a los dgitos de los nmeros naturales de entrada, en este caso

0,1,2.

q K: Es el estado Inicial

F K: F= q0, q1, q4, q5 representa el estado final

: K x P( K): : {q0, q1, q2, q3, q4, q5 } {q0,q1, q4, q5} {q0, q1, q2, q3, q4, q5 } q { q0, q1,q4, q5 } Representa la funcin total de transicin del estado.

3. Identifique la tabla de transicin correspondiente

(q0, ) = q 1 (q0, 0 ) = q2 (q0, 1 ) = q2 (q1 , 1 ) = q2 (q1, 0 ) = q3 (q2, 1 ) = q2 (q2, 2 ) = q5 (q3, ) = q2 (q3, 2 ) = q4 (q4 , 1 ) = q2 (q4, 2 ) = q5 (q5, 1 ) = q3 (q5, 2 ) = q5

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas

vlidas que terminen en un estado halt

Verificando mediante un lenguaje de cadenas y sus tipos que pueden reconocer: L= {, E( 0, 1 )} * Lenguaje que genera el autmata compuesto por las dgitos que pertenecen al conjunto de los nmeros naturales para que cumpla cierta condicin donde puede comenzar con un 0 o muchos 0(s) o con un 1 o muchos 1(s)

0 1 2

#q0 q

2 q

2 q

1

# q1 q

3 q

2

q2 q

2 q

5

q3 q

4 q

2

# q4 q

2 q

5

# q5 q

3 q

5

5. Encuentre la expresin regular vlida.

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 (eso significa que

debe hacerla por ambos lados y verificar cual es vlida sustentando el por

qu). Plsmela en el simulador y recrela. (Debe quedar documentado en el

texto el paso a paso que realizan en el simulador)

Las gramticas son mecanismos generadores de lenguajes, es decir, nos dicen cmo podemos obtener o construir palabras de un determinado lenguaje. Descripcin gramtica 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 R = Es el conjunto de reglas, es un subconjunto finito de V x (V U ) S=Es el smbolo inicial y es un elemento de V Estas gramticas regulares son de la forma: Lineales por la derecha. - Cuando todas las producciones tienen la forma A aB o bien A a Lineales por la izquierda.- Cuando todas las producciones tienen la forma A Ba o bien A a

Ya tenemos la gramtica en la nueva ventana

Como es una gramtica lineal por la derecha seleccionamos la opcin Convert Right Lineal Grammar to FA en el men Convert

Pinchamos en Show All y Export lo que nos creara un autmata equivalente a la gramtica

7. Realice el rbol de Derivacin de esa gramtica

Modelamos la gramtica

Para generar el rbol de derivacin utilizamos la opcin Brute Force Parse en el

men Input que nos abrir una nueva pestaa

Introducimos 1122122 en la caja de texto y pinchamos en Start esperamos que

acepte la palabra para luego presionar en el botn step hasta obtener el rbol de

derivacin completo que es el siguiente

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

de su afirmacin

Una gramtica es ambigua si permite construir dos o ms rboles de derivacin

distintos para la misma cadena. Por lo tanto, para demostrar que una gramtica es

ambigua lo nico que se necesita es encontrar una cadena que tenga ms de un

rbol de derivacin.

Y para verificar que esta misma gramtica nos genera dos arboles diferentes,

abrimos otra pestaa mas, cambiando el orden de las producciones.

Por ejemplo si tenemos:

S 0B CAMBIAMOS S B0

Y validamos la misma cadena que realizamos en la otra gramatica en este caso

1122122 y damos Start.

Como en este caso no genera mas arboles podemos decir que no es ambigua.

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

ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR O YA MINIMIZADO:

1. Explicar el proceso de Minimizacin (que estados se suprimen y porque).

Realice la tabla de estados distinguibles.

Cmo se soluciona: Recordemos el teorema 7: Dos autmatas M1 y M2 son

equivalentes, M1 M2, cuando aceptan exactamente el mismo lenguaje.

Para saber si dos estados q1 y q6 son equivalentes, se les pone a ambos como

estado inicial de sendos autmatas M1 y M2 , y se procede a comparar dichos

autmatas. Si stos ltimos son equivalentes, quiere decir que los estados q1 y q6

son equivalentes.}

Si dicha comparacin de AFDs da un resultado de equivalencia, se concluye que

los estados son redundantes

. Una vez que se sabe que dos estados son equivalentes, se puede pensar en

eliminar uno de ellos, para evitar redundancias y hacer ms eficiente a AFD. Sin

embargo, la eliminacin de un estado en el AFD plantea el problema de qu hacer

con las flechas que conectan al estado eliminado con el resto del autmata. Esta

cuestin se resuelve con los siguientes criterios:

Las flechas que salen del estado eliminado son eliminadas.

Las flechas que llegan al estado eliminado son redirigidas hacia su estado

equivalente.

MTODOS PARA LOCALIZAR ESTADOS REDUNDANTES Y MINIMIZAR AFDs

1. DEFINIMOS EL AUTMATA E IDENTIFICAMOS LO QUE VA A

CAMBIAR:

Entrada: (el autmata inicial sin minimizar) : Un : M =(K, , q , , F)

donde: = {0,1,2} q Es el estado Inicial F = q0,q1,q4,q5 y K = {q0,

q1, q2, q3, q4, q5}

Salida: (un AFD mnimo como resultado): M = (, K, , q0 , F)

(ntese que el alfabeto no cambia)

2. ELIMINAR ESTADOS INACCESIBLES DE M;

En la figura se han identificado los estados q4 y q2 como candidatos a ser

comparados para eliminar (en este caso q4).

Claramente se ve que el estado q0 es inaccesible, (o le llegan transiciones

adems) por tanto, se puede eliminar este estado y sus transiciones. Quedando

como estado inicial q2

Claramente se ve que el estado q1 es inaccesible, (o le llegan transiciones

adems) por tanto, se puede eliminar este estado y sus transiciones

3. IDENTIFICAR ESTADOS DISTINGUIBLES:

Vamos a definir la nocin de estados distinguibles, que intuitivamente

quiere decir que si dos estados son distinguibles, ya no pueden ser

equivalentes. La definicin es inductiva:

Los estados p y q son distinguibles si son incompatibles (es decir, uno es

final y el otro no final). Esta es la base de la induccin. Se puede verificar el

ejercicio.

Teorema 9: Dos estados son equivalentes (o redundantes) si no son

distinguibles. Es relativamente sencillo verificar si dos estados son

distinguibles.

4. CONSTRUCCIN DE TABLA:

Construir tabla T con filas desde q1 hasta qn y columnas desde q0 hasta qn-1

Q0 Q1 Q2 Resultado final: Al final quedan PAR (q4,q2)

y por lo tanto: q2 q4

Y el autmata cociente (mnimo) es: M ( { [q2] , [q3] , [q5] } , {1,2} , , [q2] , [q5] } ) Note que se han eliminado los estados q0, q1, q4 Se cambio el estado inicial a q2 y solamente se conservo el estado final q5

X

X

X

X

Q1

Q2

Q3

X

X

2. Que transiciones se reemplazan o resultan equivalentes

Se remplazan:

Antes el estado inicial era q0 ahora es q2.

Antes tenamos 4 estados finales en este quedo uno q5

La transaccin que cambio fue (q3, 2 ) = q4 ahora (q3, 2 ) = q2

Las equivalentes son q2 q4

3. Escribir la funcin de transicin del nuevo autmata

(q2, 1 ) = q2 (q2, 2 ) = q5 (q3, ) = q2 (q3, 2 ) = q2 (q5, 1 ) = q3 (q5, 2 ) = q5

4. Identificar la expresin regular (explicarla en la lectura matemtica que

se le debe hacer).

1*(2(2*(1(2+))))

5. Compruebe una cadena vlida para esa expresin regular

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

L= {, E( 1 )} *

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

Gramtica del autmata

Demostracin de una cadena valida

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

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

10. Identificar sus tablas de Transicin (plasmarlas)

11.Plasmar los pasos de minimizacin en el simulador (comprelos con el proceso manual que est explicando) y capturar los procesos en imgenes para ser documentadas en el texto.

1 2

q2 q

2 q

5

q3 q

2 q

2

# q5 q

3 q

5

AUTOMATA MINIMIZADO EN JFLAP

AUTOMATAS MINIMIZADO Y SIN MINIMIZAR Y CADENAS ACEPTADAS

PARTE 2: Disee un APD que acepte cadenas de este tipo (con pila vaca): {(abc)

(aabcc) (aaabccc) (aaaabcccc) (aabccccc) ( abccccc) (aabcccc)

(aaaaaabcccccccccc) (aaabccccc) (aaabccccccccccc)}

Cadenas no vlidas. {(bcc) (ac) (aabc9 (aaaabcc) (aaaccccb) (acb) (aaaaabcc)

(aaabcc)}

1. Describa el autmata en notacin matemtica, y encuentre en primera

instancia una regla que evale estas cadenas y que cumpla las

condiciones de las mismas.

Dado el siguiente Autmata M Finito: M =(K, , q , , F) donde:

K = {q0, q1, q2, q3} = {a,b,c} q Es el estado Inicial F = q3

donde la funcin de transicin est dada por: : {q0, q1, q2, q3 } {a,b,c} {q0, q1, q2,

q3} q { q3}

(q0, a ) = q 0 (q0, a ) = q1 (q1, b ) = q2 (q2 , c ) = q3 (q3, c ) = q3

2. Grafquelo en JFLAP y realice el Traceback para las transiciones.

(Las columnas para un AP son: El estado en que se encuentra el

autmata, lo que falta por leer de la palabra de entrada, y el contenido

de la pila).

ESTADO POR LEER PILA

Q0 aabcc

Q0 abcc a

Q1 bcc aa

Q2 cc aab

Q3 c aabc

Q3 aabcc

3. Plasme las imgenes y capturas en el documento. (Documente el

proceso)

4. Muestre el diagrama correspondiente de estados.

5. Identifique los contenidos (el recorrido para cada interaccin) de la pila y

el estado de parada. Realcelo con una cadena vlida.

Para comprobar la validez de esta cadena hacemos click en input luego nos

vamos a step with closure, nos aparece otra ventana all digitaremos las cadenas

que deseamos comprobar y le diremos que hasta el estado final, seguido daremos

click en step para recorrer el automata por cada uno de sus estados hasta el

estado final.