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)

...