AUTOMATAS Y LENGUAJES FORMALES

MOMENTO 2

LUIS CARLOS SANTANA BERNAL COD: 1070963683BORIS ESTIVEN PALACIOS ALARCON: 1140819557OSCAR ALEXANDER HERNANDEZ COD:

PRESENTADO A: JAIME RUBIANO LLORENTETUTOR DE AUTOMATAS Y LENGUAJES FORMALES

GRUPO: 301405_18

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

BARRANQUILLA, 10 DE JULIO DEL 2015ContenidoINTRODUCCION4OBJETIVOS5Calcular el autmata mnimo correspondiente al siguiente autmata finito.6Autmata No Minimizado:6Expresin Regular de Autmata No Minimizado:6Autmata Minimizado:6Expresin Regular de Autmata Minimizado:7Enuncie el autmata en notacin matemtica.7Identifique la tabla de transicin correspondiente7Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas vlidas que terminen en un estado halt8Encuentre la expresin regular vlida.0Encuentre su gramtica que sea vlida para la funcin de transicin (describa sus componentes y como se escriben matemticamente).0Genere la gramtica tanto por la izquierda como por la derecha y verifique cual es vlida sustentando el por qu.1Gramtica por la derecha1Gramtica por la izquierda1Realice el rbol de Derivacin de esa gramtica.0Identifique si ese rbol o gramtica es ambigua o no y plasme las razones de su afirmacin.2ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR Y YA MINIMIZADO3Identifique los estados No distinguibles y los Distinguibles. Justifique o caracterice la diferencia entre ellos.3Identifique los estados equivalentes. Para ello realice el proceso de validacin de equivalencias identificando los estados a ser eliminados.4Esto se puede verificar aplicando la minimizacin por conjuntos:4Realice el proceso de eliminacin de estados (que estados se suprimen y porque). Realice la eliminacin de transiciones y de estados.7Realice la tabla de estados distinguibles.8Escribir la funcin de transicin del nuevo autmata.8Identificar la expresin regular (explicarla en la lectura matemtica que se le debe hacer).9Identificar el lenguaje que reconoce y cinco posibles cadenas vlidas.9El autmatas nuevo expresarlo o graficarlo con su respectivo diagrama de Moore.10Identificar sus tablas de Transicin10Disee un AP que dentro de su lenguaje L ={ab}* ;es decir todas las combinaciones posibles de cadenas conformadas por los smbolos (a) (b) o conjunto universal de estrellas de kleene, (con pila vaca): exceptuando o rechazando cadenas como:11Describa el autmata en notacin matemtica.11Determine el lenguaje que reconoce el AP.11Justifique y asocio o evidencie si el diseo es un APND o un APD12Grafquelo 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).12Plasme las imgenes y capturas en el documento. (Documente el proceso)13Muestre el diagrama correspondiente de estados.14Identifique los contenidos (el recorrido para cada interaccin) de la pila y el estado de parada. Realcelo con una cadena vlida.15Determine si su diseo acepta o no la cadena vaca y explique por qu en cualquier caso, demostrando el recorrido o comportamiento de la Pila. (Evidencindolo).15

INTRODUCCION

Con el desarrollo del siguiente trabaja so pretende demostrar que se han adquirido los conocimientos con respecto a la minimizacin de los autmatas, y su funcionamiento.Tambin es importante complementar la solucin de los ejercicios de la actividad a travs del uso de herramientas computacionales de simulacin, empleando los conceptos aprendidos en nuestros estudios de las diversas ramas de la Ingeniera en nuestra Universidad, El siguiente trabajo muestra dos ejercicios realizados por el trabajo colaborativo y como se integraron los resultados de las personas para mostrar un trabajo final concluyente.

OBJETIVOS

Reconocer los lenguajes independientes del contexto y sus diversas aplicaciones. Analizar la estructura de las gramticas independientes del contexto. Estudiar el concepto de los autmatas de pila, su funcionamiento y los lenguajes utilizados. Distinguir los lenguajes independientes del contexto existentes y sus propiedades, as como los algoritmos de decisin. Generalizar los conceptos de autmatas finitos y gramticas regulares. Reconocer el potencial de procesamiento del lenguaje del autmata con los Autmatas de pila.

Calcular el autmata mnimo correspondiente al siguiente autmata finito.Autmata No Minimizado:

Expresin Regular de Autmata No Minimizado:

((01+10+(00+11)(0+111)*110+(00+11)(0+111)*10(0(0+111)*10)*(1+0(0+111)*110))1*0)*(01+10+(00+11)(0+111)*110+(00+11)(0+111)*10(0(0+111)*10)*(1+0(0+111)*110))1*Autmata Minimizado:

Expresin Regular de Autmata Minimizado:

((110*1+000*1)*(10+01)1*0)*(110*1+000*1)*(10+01)1*

Enuncie el autmata en notacin matemtica.

M = {q0,q1,q2,q3,q4},{0,1},,{q1},{q4} donde K = { q0,q1,q2,q3,q4 } = {0,1}, S= q1 F= q4M es un quntuplo (K, , , s, F), donde:K = {q0, q1, q2, q3, q4}, identifica el conjunto de estados del autmata = {0,1}, es el alfabeto de entrada = es la funcin de transicin, que a partir de un estado y un smbolo del alfabeto obtiene un nuevo estado. s es el estado inicial, en nuestro caso q1F es un conjunto de estados finales, en nuestro caso q4

Identifique la tabla de transicin correspondiente

f01

q0q0q1

q1q3q2

q2q4q0

q3q0q4

#q4q1q4

: K x K es la funcin de transicin, que a partir de un estado y un smbolo del alfabeto obtiene un nuevo estado : {q0,q1,q2,q3,q4} x{0,1} {q0,q1,q2,q3,q4} {q1} {q4}

Viene dada por:

(q0,0)=q0 (q0,1)=q1 (q1,0)=q3 (q1,1)=q2 (q2,0)=q4 (q2,1)=q0 (q3,0)=q0 (q3,1)=q4 (q4,0)=q1(q4,1)=q4

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

L= {A {0,1}*| A={.El lenguaje que reconoce ser el de todas las posibles cadenas que empiezan por 0 o por 1 yque terminan en 0 o 1, seguidos de una combinacin de uno o varios 0 o 1.bajo ciertas condiciones (propiedades) que resultan complejas (ER), por eso es que se reduce o minimiza el autmata.

1. Encuentre la expresin regular vlida.

((110*1+000*1)*(10+01)1*0)*(110*1+000*1)*(10+01)1*Con Fjlap

Encuentre su gramtica que sea vlida para la funcin de transicin (describa sus componentes y como se escriben matemticamente).

Definimos o caracterizamos una gramtica regular como:Un cudruplo (V, , R, S) en donde:G = ({S, D, A, B, C}, {0,1}, {S0C, S1B, D1D,A0A,B0D,B1A,C1D,D0S,C0A,A1S,D}, S)V = Es el alfabeto de variables V = {S, D, A, B, C} = Es el alfabeto de constantes = {0,1}R = Es el conjunto de reglas, es un subconjunto finito de V x (V U )

S0C

S1B

D1D

A0A

B0D

B1A

C1D

D0S

C0A

A1S

D

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

Genere la gramtica tanto por la izquierda como por la derecha y verifique cual es vlida sustentando el por qu.

Gramtica por la derecha

S0C

S1B

D1D

A0A

B0D

B1A

C1D

D0S

C0A

A1S

D

Esta gramtica regular es Lineal por la derecha, porque al desarrollarse cada cadena, las variables se despejan por la derecha formando la cadena que entra y es aceptada.

Gramtica por la izquierda

SFM

C

FBV

CBF

DBD

VBD

EBC

B0

A1

M

FAE

DAF

EAD

VAC

CAC

Al analizar las gramticas, podemos concluir que tanto la gramtica por la derecha y por la izquierda son vlidas, debido a que reconocen el mismo leguaje y generan las mismas cadenas vlidas y no vlidas.

Realice el rbol de Derivacin de esa gramtica.

CADENAS AVALUADASRBOL DE DERIVACIN

10

101

00101

000110

01001

011010

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

La gramtica no es ambigua debido a que el autmata es determinstico, por cuanto siempre nos una sola ruta para llegar al estado final, como evidencia en el siguiente rbol de derivacin.

CADENA VALIDARBOL DE DERIVACIN

011010

ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR Y YA MINIMIZADO:Identifique los estados No distinguibles y los Distinguibles. Justifique o caracterice la diferencia entre ellos.

Distinguibles (Estados NO Finales)No Distinguibles (Estados Finales)

Los estados q0,q1,q3,q4,q5,q6,q7 son distinguibles debido a que son estados no finales y son diferentes a q2 el cual es el estado final.

Identifique los estados equivalentes. Para ello realice el proceso de validacin de equivalencias identificando los estados a ser eliminados.

Se eliminara q3 ya que es un estado inaccesible, es decir que ningn estado puede llegar a l.q1 y q7 son equivalentes ya que con 0 van a q6 y con 1 van a q2.q0 y q4 son equivalentes (una vez se minimice q1 con q7) ya que con 0 van a q1 y con 1 van a q5.

Esto se puede verificar aplicando la minimizacin por conjuntos:

Se separan los estados finales de los no finales y a cada uno se le asigna un conjunto en este caso X para NO Finales y Y para FinalesEstados NO FinalesEstados Finales

= X=Y

A los conjuntos se los evala segn con alfabeto y el autmata analizado dependiendo del resultado se mira a que conjunto pertenece este resultado ejemplo analizamos se evidencia que el resultado es este pertenece al conjunto de los NO Finales por tanto pertenecera al conjunto de las X entonces se coloca una X en su lugar

ESTADOS FINALES

Alfabeto Estados01

#XY

ESTADOS NO FINALES

Alfabeto Estados01

q0XX

q1XY

q3YX

q4XX

q5YX

q6XX

q7XY

Se analizan las tablas y se miran que conjuntos comparten las mismas caractersticas para emparejarlos y formamos nuevos conjuntos, si los conjuntos son iguales se los deja tal cual como en el caso del conjunto X

CONJUNTO X

Alfabeto Estados 01

ZY

ZY

XX

Se evalan los nuevos conjuntos con alfabeto y el grafico del autmata.CONJUNTO Y

Alfabeto Estados 01

ZX

ZX

CONJUNTO Z

Alfabeto Estados 01

XZ

XZ

XZ

Se

Pueden forman nuevos conjuntos y se evalan con el alfabeto y el grafico del autmata CONJUNTO N

Alfabeto Estados 01

ZY

ZY

CONJUNTO X

Alfabeto Estados 01

XN

CONJUNTO Z

Alfabeto Estados 01

XZ

NZ

XZ

CONJUNTO Y

Alfabeto Estados 01

ZX

ZX

CONJUNTO X

Alfabeto Estados 01

XN

CONJUNTO N

Alfabeto Estados01

ZY

ZY

CONJUNTO Y

Alfabeto Estados 01

MX

MX

CONJUNTO Z

Alfabeto Estados 01

XM

XM

CONJUNTO M

Alfabeto Estados 01

NM

Como se mira en las tablas hay 5 conjuntos que comparten las mismas caractersticas, estas 5 tablas son los 5 nuevos estados ESTADO INICIAL (es que es el estado inicial) ESTADO FINAL

Se arma el nuevo autmata con sus estados sacados de las tablas anteriores

Realice el proceso de eliminacin de estados (que estados se suprimen y porque). Realice la eliminacin de transiciones y de estados.

ESTADO A ELIMINARCAUSA DE LA ELIMINACIN

q3Se eliminara q3 ya que es un estado inaccesible, es decir que ningn estado puede llegar a l.

q7Se eliminara q7 ya que es equivalente con q1 debido a que con 0 van a q6 y con 1 van a q2.

q4Se eliminara q4 ya que es equivalente con q0 (una vez se minimice q1 con q7) debido a que con 0 van a q1 y con 1 van a q5.

Realice la tabla de estados distinguibles. No se utiliza q3 ya que se elimina por ser un estado inaccesible.

q1X

q2

q4(q1,q7)X

q5XXX

q6XXXX

q7XXXXX

q8XXXXXX

q0q1q2q4q5q6q7

Por lo tanto q1 ~ q7 y q0 ~ q4 y el autmata cociente mnimo es:M = {q0,q1,q2,q3,q4},{0,1},,{q1},{q4}Ntese que se elimin q3, q4 y q7.

Escribir la funcin de transicin del nuevo autmata.

K = { q0,q1,q2,q3,q4}, identifica el conjunto de estados del autmata

= {1, 0}, es el alfabeto de entradas es el estado inicial, en nuestro caso {q1}

F es un conjunto de estados finales, en nuestro caso {q4} : K x K es la funcin de transicin, que a partir de un estado y un smbolo del alfabeto obtiene un nuevo estado : {q0,q1,q2,q3,q4} x{0,1} {q0,q1,q2,q3,q4} {q1} {q4}

Viene dada por:

(q0,0)=q0 (q0,1)=q1 (q1,0)=q3 (q1,1)=q2 (q2,0)=q4 (q2,1)=q0 (q3,0)=q0 (q3,1)=q4 (q4,0)=q1(q4,1)=q4 Identificar la expresin regular (explicarla en la lectura matemtica que se le debe hacer).

Expresin Regular de Autmata Minimizado:((110*1+000*1)*(10+01)1*0)*(110*1+000*1)*(10+01)1*

Identificar el lenguaje que reconoce y cinco posibles cadenas vlidas.

L= { {1, 0} | ((110*1+000*1)*(10+01)1*0)*(110*1+000*1)*(10+01)1*}La forma matemtica del lenguaje del autmata: L= {(110 n1, 000m1) , (10,01)1o0)p(110q1,000r1)s(10,01)1t} n, m, ,o,p,q,r,s,t 0}TEMCADENAS VALIDAS

110

2101

300101

4000110

501001

6011010

El autmatas nuevo expresarlo o graficarlo con su respectivo diagrama de Moore. Expresin Regular de Autmata Minimizado:((110*1+000*1)*(10+01)1*0)*(110*1+000*1)*(10+01)1*

Identificar sus tablas de Transicin

f01

q0q0q1

q1q3q2

q2q4q0

q3q0q4

#q4q1q4

Con base en la informacin obtenida en la tabla de transicin, se puede afirmar que se trata de un autmata tipo AFD (autmata finito determinstico), por cuanto siempre nos una sola ruta para llegar al estado final.

Disee un AP que dentro de su lenguaje L ={ab}* ;es decir todas las combinaciones posibles de cadenas conformadas por los smbolos (a) (b) o conjunto universal de estrellas de kleene, (con pila vaca): exceptuando o rechazando cadenas como:

Cadenas no vlidas. Las que estn compuestas por uno o muchos smbolos b: ejemplo: {(b) (bb) (bbb) (bbbb)(bbbbb) (bbbbbb) (bbbbbbb) (bbbbbbbb) (bbbbbbbbb) . } En el diseo que haga es libre determinar si acepta la cadena vaca o no.

Describa el autmata en notacin matemtica.

M = ({q0,q1} , {a,b} ,{z0,1} ,, q0)

La formalizacin de un autmata de pila es un sptuplo (K, ,,, s, F) en donde:K = {q0,q1} es el conjunto de estados = {a,b} es el alfabeto de entrada = {z0,1} es el alfabeto de la pilaS K = = {q0} es el estado inicialZ0 es el smbolo inicial de la pila (o tambin se denota como Z simplemente)F K = {q0} es un conjunto de estados finales. (K x * x *) x (K x *) es la relacin (funcin) de transicin.

Determine el lenguaje que reconoce el AP.

L= { {a, b} | {ab}n}La forma matemtica del lenguaje del autmata:L= {ab}n n 0}

Justifique y asocio o evidencie si el diseo es un APND o un APD

El diseo es una autmata de pila no determinista (APND) ya que dado un estado, un smbolo del alfabeto de entrada y otro del alfabeto de la pila, puede pasar a distintos estados y reemplazar el tope de la pila por distintas cadenas i, avanzando o no la cabeza lectora una posicin.Lo anterior lo podemos demostrar y sintetizar como:(q,,a) (K x V x )

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).Cadena: abab

ESTADOPOR LEERPILA

q0ababZ0

q1bab1

q0abZ0

q1b1

q0Z0

Plasme las imgenes y capturas en el documento. (Documente el proceso)

DESCRIPCINIMAGEN SIMULACIN

0La cadena valida que esta lista para leer es abab, inicia en el estado q0, y la Pila esta en Z0

1Lee la primera a y se traslada al estado q1, se introduce un 1 a la pila y no se extrae nada.

2Lee la primera b y se traslada al estado q0, se saca un 1 a la pila y no se introduce nada.

3Lee la segunda a y se traslada al estado q1, se introduce un 1 a la pila y no se extrae nada.

4Lee la segunda b y se traslada al estado q0, se saca un 1 a la pila y no se introduce nada, quedando as aceptada la cadena y la pila en z0.

Muestre el diagrama correspondiente de estados.

ESTADOPOR LEERPILA

q0ababZ0

q1bab1

q0abZ0

q1b1

q0Z0

Identifique los contenidos (el recorrido para cada interaccin) de la pila y el estado de parada. Realcelo con una cadena vlida.ESTADOPOR LEERPILA

q0ababZ0

q1bab1

q0abZ0

q1b1

q0Z0

Cadena: abab

Determine si su diseo acepta o no la cadena vaca y explique por qu en cualquier caso, demostrando el recorrido o comportamiento de la Pila. (Evidencindolo).

El diseo acepta la cadena vaca, toda vez que el autmata termina de evaluar los estados cuando ya no hay estados por leer, por cuanto este se queda en el estado aceptador, convirtiendo la cadena vaca en una cadena valida.ESTADOPOR LEERPILA

q0Z0

BIBLIOGRAFIAMODULO AUTMATAS Y LENGUAJES FORMALES

Gramticas formales http://gramaticasformales.wordpress.com/Gramatica libre de contexto a pilahttp://luzem.dyndns.org/tag/gramatica-libre-de-contexto-a-automata-de-pila/

lengujaes libres de Contextohttp://teodelacomp.blogspot.com/2011/03/automatas-pushdown-presentan-ing.html

Minimizacion de un autmatahttp://www.youtube.com/watch?v=jd4cQ9yJj2c

Automata de pila http://www2.dis.ulpgc.es/~mluengo/automatas/teoria/tema4.pdf