Como son las Automtas y lengiajes formales 1. unad

TRABAJO COLABORATIVO 1

GRUPO: 301405_58

ESTUDIANTE:

FERNANDO OTALORA PERDOMO

COD. 1.075.245.925

RONALD NINCO

COD. 7.716.564

TUTORA:

ANGELA MARIA GONZALEZ

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

PROGRAMA DE INGENIERÍA DE SISTEMAS

NEIVA - SEPTIEMBRE DE 2015

DESCRIPCIÓN GENERAL DEL TRABAJO

En este trabajo analizaremos los tipos de autómata finitos, las expresiones regulares y las propiedades de los lenguajes regulares, veremos cada uno de los elementos y restricciones de estos y en que consiste cada uno de ellos, dándole solución a cada uno de los ejercicios propuestos en la guía de actividades.

Los autómatas y lenguajes formales, son muy importantes en nuestra formación profesional, para estudiar, analizar y profundizar los conceptos fundamentales de la teoría del diseño y manejo de variables, por ello Vamos a tratar de afianzar algunos conocimientos sobre los temas de autómatas y lenguajes formales tales como lenguajes regulares formulando el desarrollo de una serie de ejercicios.

DESARROLLO

1.  Las expresiones regulares (ER), pueden también escribirse de otras formas o con otra secuencia de operadores o distribución de símbolos. En general es una forma matemática que representa el Lenguaje que genera un Autómata. Y esas expresiones regulares siempre serán válidas siempre y cuando representen exactamente el mismo lenguaje para un Autómata. Concluyendo, para un Autómata, puede haber más de una ER que representa el mismo lenguaje ya sea que esa ER sea minimizada, extensa, equivalente o como se prefiera escribir. Solo que en los diseños óptimos computacionales siempre se buscará la mejor ER (corta o mínima) para efectos de la mejor simulación o para llevarlas a lenguajes de programación en la creación de soluciones computacionales (solucionar problemas - Algoritmos)

Dada las siguientes expresiones regulares (ER), encuentre la expresión mínima simplificada correspondiente y una posible expresión equivalente escrita de otra forma. (Para ello, siempre tenga en cuenta la jerarquía de caracteres y el tema de ER descrito en el módulo).

1. Describa la forma matemática del autómata.

Rpta:

Dado el Autómata, en donde  M finito:

[pic 47]

 [pic 48]

Función de transición:

δ: {q0, q1} x {0,1} → {q0, q1} → q0 →{q1}

[pic 49]

[pic 50]

[pic 51]

[pic 52]

Se plasma la gráfica obtenida por medio del simulador JFLAP

[pic 53][pic 54][pic 55]

2. Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo sino de justificarlo asociando la respuesta al diseño del autómata)

• Cada fila corresponde a un estado q.
• El estado inicial se precede del símbolo [pic 58]
• Cada estado final se precede del símbolo #
• Cada columna corresponde a un símbolo de entrada.

Autómata Finito Determinísticos:

Porque me está determinando la ruta por donde puedo pasar,  recrear o correr las cadenas que puede aceptar el autómata.

3. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.

5-tupla: (K, Σ, q°, δ, F) donde:

• Σ    Es el alfabeto que contiene estos símbolos = (1,2,3).
• K son los estados que tiene este autómata =[pic 59]
• q°  es el estado Inicial = ;[pic 60]
• δ Es la  función  de  transición que indica  a  qué estado se va a pasar sabiendo cuál es el estado actual  y el símbolo que se está leyendo, en donde la función δ: (q1,q2,q3)*({1,2,3)  Viene dada por:[pic 61]

[pic 62]

[pic 63]

[pic 64]

4. Identifique el lenguaje que genera.

L={w ϵ (0,1)*}|w= (1+0)*

5. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)

[pic 65]

• Ingresamos la cadena 10101 es una cadena aceptada.  

• Iniciamos el autómata en  q0  que es la entrada.

• La cadena aceptada 10101 inicia con un (0) el cual toma el camino y puede realizar el cambio estado hacia q1.

• Termina en el estado q1, y hace un ciclo repetitivo para terminar el recorrido de la cadenas restantes  10101.

1. Muestre el diagrama de Moore generado en JFLAP y en VAS y comente tres similitudes y tres diferencias que encuentra al realizarlo en los dos simuladores. (herramientas que ofrezca uno u otro).

DIAGRAMA DE MOORE VAS

[pic 66]

DIAGRAMA DE MOORE JFLAP

[pic 67]

Similitudes:

• En los dos simuladores se pueden guardar los autómatas creados.
• Permiten la conversión del autómata de NFA a DFA
• Permiten establecer claramente si una cadena es aceptada o rechazada por el autómata de acuerdo al diagrama de Moore.
• Se pueden crear autómatas finitos determinísticos y no determinísticos

 Diferencias:

• El JFLAP traer botones para deshacer y rehacer, mientras que el VAS no.
• En el JFLAP podemos escribir expresiones regulares, las cuales podemos convertirla en un autómata finito no determinístico.
• En el JFLAP los estados salen con sus respectivos nombres mientras que en el VAS hay que colocarlos de forma manual.

1. Genere tres cadenas válidas y dos no válidas.

[pic 68]

[pic 69]

Cadenas validas:

• 1001
• 111110
• 101

Cadenas no validas

• 111111111
• λ

1. Si el autómata inicial (el de la ER4) es un AFD, genere un AFND que reconozca el mismo lenguaje; o por lo contrario si el autómata inicial es un AFND, genere un AFD que reconozca el mismo lenguaje.

1. Describa la forma matemática del autómata

Para este proceso renombramos dos nuevos estados inicial y final con transiciones nulas, como ilustra el diagrama.

[pic 70]

El paso a seguir es la eliminación de los nodos.

[pic 71]

[pic 72]

Obteniendo de esta manera la nueva ER

ER= [pic 73]

1. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto).

En este caso la 5-tupla sería:

[pic 74]

[pic 75]

= [pic 76][pic 77]

S = [pic 78]

F= [pic 79]

Tal como se puede ver, podemos encontrar que para construir las diferentes rutas, podríamos repetir 1 varias veces dado lo que muestra  o incluso no ponerlo en la cadena, lo mismo pasaría en el 1 con  y  ó el 0 en . [pic 80][pic 81][pic 82][pic 83]

...