mom2_nilsaatehortua

7/23/2019 Mom2_NilsaAtehortua

1/18

AUTOMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO 2

PRESENTADO PORNILSA GLADYZ ATEHORTUA GALEANO-1099546747

GRUPO: 301405_29

TUTORAANGELA MARIA GONZALEZ

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

CIMITARRA SANTANDERCOLOMBIA

08/10/2015


2/18

INTRODUCCION

La teora de autmatas es el estudio de dispositivos de clculo abstractos, en pocas palabras,

de las mquinas. Antes de que existieran las computadoras, en la dcada de los aos treinta,

A. Turing estudi una mquina abstracta que tena todas las capacidades de las computadoras

de hoy da, al menos en lo que respecta a lo que podan calcular.

El fundamento ms importante o esencial para el estudio de los lenguajes y autmatas es la

Teora de Conjuntos. En efecto, siempre que hablemos de formalizar una nocin, estaremos

diciendo en realidad expresar en trminos de la Teora de Conjuntos. El objetivo de las

expresiones regulares es representar todos los posibles lenguajes definidos sobre un alfabeto

, en base a una serie de lenguajes primitivos, y unos operadores de composicin.


3/18

PROBLEMAS A DESARROLLAR:

PARTE 1: HALLAR EL AUTMATA MNIMO CORRESPONDIENTEal siguiente

autmata finito.

Importante:El proceso de minimizacin no se debe hacer de forma automtica en JFLAPpor que no ser vlido para asignacin de puntos en la rbrica. JFLAP lo puede usar paravalidar o demostrar algunos pasos o procesos pero no para la minimizacin automtica. Para

la obtencin de las gramticas, estas deben generarse de forma manual (no con JFLAP).


4/18

Puede usar JFLAP para demostrar por ejemplo cadenas aceptadas o no por las gramticas, ypara los rboles de derivacin pero no para generar las gramticas.

1. Realice la descripcin (notacin) (caracterizacin) matemtica del autmata. (Antes

de minimizar)

La frmula matemtica se expresa por:

A= (Q,, ,,F), para nuestro caso la forma matemtica sera:

A = ({, , , , , , , , },{0,1},,, {, , })

Donde:

= { , , , , , , , , }={0,1}s = , estado inicialF = {, , }, estados finales

Entonces:

La funcin = {, , , , , , , , } {0,1} {, , , , , , , , },viene dada por:

, 0 = , 1 =

, 0 = , 1 = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 =

2. Plasme la tabla de transicin del autmata. (Antes de minimizar)

A

Q 0 1


5/18

3. Identifique El Lenguaje que reconoce. (Antes de minimizar)

El lenguaje que reconoce el autmata es:

L= {w | #2 = 0

#2 = 0}.

Esto expresa que el autmata acepta o admite todas las palabras que inicien con mnimo un

par de 1s, o mnimo un par de 0sy seguido de pares de 1sy 0s.

4. Identifique la ER y en una tabla de validacin (puede ser de Excel), verifique unacadena vlida y una no vlida. Tenga en cuenta la jerarqua de operadores. (Antes deminimizar)

CADENAS VALIDAS CADENAS NO VALIDAS0000001 Rechazar

010111 Aceptar


6/18

5. Identifique los estados Distinguibles y los No distinguibles

Distinguible: Son distinguibles cuando uno estado es final y el otro es un estado normal.

No Distinguible: aquellos en los cuales se presentan como estados finales.

6. Identifique los estados equivalentes (para ello muestre cmo evala esasequivalencias, colocando a los estados candidatos de equivalencia como estadosiniciales). Evidencie el proceso de cmo los evala.

= (3, 5, 8) = 0, 1, 2, 4, 6, 7,

0.1

0 1

Estados finales aceptados

0 1

x x x x x x x x x x x x x x x x x x x x x x x x x x x x

x x x x x x x x


7/18

Continuamos

= (3, 5, 8)

= ( , , ) 1 = ( , , ) 2 = ( , , ) 3

LUEGO

= ( , , ) 1

0 1

Se genera dos conjuntos

= {0} = {4}

= ( , , ) 2

0 1

= ( , , ) 3

0 1


8/18

ENTONCES TENEMOS 5 ESTADOS QUE: = (3, 5, 8) Son estados equivalentes

0 1

= ( , , )Son estados equivalentes

0 1

= ( , , )Son estados equivalentes

0 1

= (, )Se concluye que es un estado de una sola transicin

0 1

= ( , )Se concluye que es un estado de una sola transicin0 1


9/18

Segn la validacin realizamos la nueva tabla de transicin:

0 1

7. En el proceso de eliminacin de estados, identifique que transiciones se eliminan ycules se re direccionan. Muestre la tabla de estados distinguibles

Las transiciones que se eliminaron fueron las del conjunto M, pero se re direcciono con los

nuevos conjuntos A y B, ya que se formaron dos conjuntos al no ser equivalentes y siendoestados de una sola transicin.

8. El autmata nuevo minimizado expresarlo o graficarlos en un diagrama de moore

9. Realice la descripcin (notacin) (caracterizacin) matemtica del autmata yaminimizado

La frmula matemtica viene dada por A=(Q,, ,,F), para nuestro caso la formamatemtica sera:

A = ({, , , , },{0,1},, , {})

#


10/18

Donde: = { , , , , }={0,1}s =, estado inicialF = {}, estados finales

La funcin = {, , , , } {0,1} {, , , , }, viene dada por:

, = , = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 = , 0 = , 1 =

10. Identifique El Lenguaje que reconoce. (Autmata ya minimizado)

El lenguaje que identificara el autmata es el de todas las viables y posibles cadenas que

comiencen con mnimo un par de 1, o mnimo un par de 0 y contino de pares de 1 y 0.

11. Identifique la ER del autmata ya minimizado y en una tabla de validacin (puedeser de Excel), verifique una cadena vlida y una no vlida. Tenga en cuenta la jerarquade operadores. (Autmata ya minimizado)

(1(00)*1+(0+1(00)*01)(11+10(00)*01)*(0+10(00)*1))(1(00)*1+(0+1(00)*01)(11+10(00)*01)*(0+10(00)*1))*


11/18

12. (Autmata minimizado) Identifique su gramtica (de forma manual) por la derechay caractercela Debe incluir el diagrama de estados con los componentes de lagramtica asociados a las variables y a las constantes.

En autmatas la gramtica es n conjunto de reglas para formar correctamente las frases de un

lenguaje.Donde la gramtica regular es un cudruplo (V, , R, S) adonde:

CFG G:

, , .

Las reglas de gramtica pueden ser vistas como reglas de reemplazo.

Para nuestro ejemplo quedara:

= {, , , ,}= {0,1} = 0

=

Entonces la forma de la tupla:


12/18

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

Lenguaje formado por una gramtica:L (G)= | s

S 0DS 1BA 1DD 1AA 0BB 0AC C 1BB 1CC 0DD 0C

13. Realice la gramtica por la izquierda (de forma manual) y compare si esta gramticaacepta o no el mismo lenguaje (cadenas). Justifique y demuestre su respuesta

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

14. Con una cadena vlida, genere un rbol de derivacin para la gramtica por laderecha y demuestre y justifique si la cadena y rbol generado puede ser ambigua o no.

La cadena no es ambigua ya que es un autmata determinstico.

Cadena valida: 1100


13/18

PARTE 2: Disee un AP que dentro de su lenguaje L ={ab}* ;es decir todas lascombinaciones 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.

1. Describa el autmata en notacin matemtica.

AP= {Q, V, , , q0, z0, F}

En dnde.

Q= {q0, q1}

V= {a, b}

= {Z0, , 1}

= {q0, b, Z0}= {(q0, 1Z0)}


14/18

= {q0, a, Z0}= {(q1, )}

= {q1, b, Z0}= {(q1, 1 Z0)}

2. Determine el lenguaje que reconoce el AP.

Analizando el lenguaje que reconoce el autmata de pila podemos determinar que ste,

es un lenguaje libre de contexto que contienen a los lenguajes regulares.

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

Este un autmata de pila no determinstico porque ya que con un estado cedido, un

smbolo del alfabeto de entrada y otro del alfabeto de la pila, puede pasar a diferentesestados y sustituir toda la pila por cadenas f, pudiendo adelantar la cabeza lectora de la

pila.

El autmata generado o creado por JFLAP, logramos ver que no se sabe en donde puede

estar la cabeza lectora de la pila con certeza, entonces obtenemos expresar que se trata de

un autmata de pila no determinstico.


15/18

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

Imagen en flap

Traceback para transicin tenemos.

5. Plasme las imgenes del recorrido de ese Traceback para cada movimiento en eldocumento. (Se debe apoyar en JFLAP) (Documente el proceso)


16/18


17/18

6. Muestre el diagrama correspondiente de estados.

Estado Por leer Pila

1 1

7. 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 para ese evento. (Evidencindolo).

Si se acepta la cadena vaca lo podremos demostrar con el autmata de pila ya realizado.


18/18

CONCLUSIONES

Se puede concluir de la siguiente actividad, que se cumplieron los objetivos del trabajo

porque se logr establecer y conceptualizar las aplicaciones y contenidos temticos en elestudio del mdulo, as como de otras fuentes bibliogrficas.

Tambin se lograron determinar e interactuar las temticas de gramtica, expresiones

regulares, lenguajes formales, autmatas finitos, las cuales se han logrado comprenderclaramente.

REFERENCIAS BIBLIOGRAFICAS

MINIMIZAR AUTOMATAS PARTE 1Recuperado de:

https://www.youtube.com/watch?v=z19KDUC1oh0

MINIMIZAR AUTOMATAS PARTE 2Recuperado de:https://www.youtube.com/watch?v=LThVITEsLiA

MINIMIZAR AUTOMATAS PARTE 3Recuperado de:https://www.youtube.com/watch?v=Sto4KosrUX8

MINIMIZAR AUTOMATAS PARTE 4Recuperado de:https://www.youtube.com/watch?v=d0-Nkk3Y1DU

Autmatas de pila 1Recuperado de:

https://www.youtube.com/watch?v=-I7o_Qip4wY

mom2_nilsaatehortua

Documents