Trabajo Colaborativo 2 Automatas Y Lenguajes Formales

TRABAJO COLABORATIVO 2

AUTOMATAS Y LENGUAJES FORMALES

RICHARD GRANADOS GOMEZ

EDWIN LARA GALLO

JORGE ARMANDO BARRETO

UNIVERSIDAD ABIERTA Y A DISTANCIA UNAD

NOVIEMBRE 2013

TRABAJO COLABORATIVO 2

AUTOMATAS Y LENGUAJES FORMALES

RICHARD GRANADOS GOMEZ

CODIGO: 7.601.164

EDWIN LARA GALLO

CC. 7.726.008

JORGE ARMANDO BARRETO

8.861.165

GRUPO: 301405_5

TUTOR: CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD ABIERTA Y A DISTANCIA UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

NOVIEMBRE 2013

INTRODUCCION

El presente trabajo está realizado con el fin de analizar y comprender los diferentes temas propuestos en la segunda unidad del modulo de Autómatas y Lenguajes Formales afianzando conocimientos sobre Autómatas finitos, gramáticas regulares, Autómatas de pila etc.

Los lenguajes independientes del contexto que también se conocen con el nombre de gramáticas de contexto libre son un método recursivo sencillo de especificación de reglas gramaticales con las que se pueden generar cadenas de un lenguaje. El propósito de la actividad es aplicar los conceptos leídos en el modulo de estudio mediante el desarrollo de ejercicios con sus respectivos diagramas de Moore y de estados en el software JFLAP

OBJETIVO

Reconocer las distintas gramáticas ya que existen diferentes formas que generan un mismo lenguaje. El hecho de no restringir la forma de las reglas se tiene interés en los casos en que se desea diseñar una gramática para un lenguaje dado.

OBJETIVOS ESPECIFICOS.

 Analizar la estructura de las gramáticas independientes del contexto.

 Estudiar el concepto de los autómatas de pila, su funcionamiento y los lenguajes utilizados. Distinguir los lenguajes independientes del contexto existentes y sus propiedades, así como los algoritmos de decisión.

 Distinguir los lenguajes independientes del contexto existentes y sus propiedades, así como los algoritmos de decisión

DESARROLLO DE LA ACTIVIDAD

1. Calcular el autómata mínimo correspondiente al siguiente autómata finito.

ACTIVIDADES ANTES DE MINIMIZAR.

Enuncie el autómata en notación matemática

M = ({q1, q2, q3, q4,q5} , {a, b} , δ, q1, {q5})

3. la tabla de transición correspondiente

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas válidas que terminen en el estado “halt”:

El lenguaje que reconoce son todas las cadenas que empiezan con a seguido de cualquier cantidad de símbolos a mas el símbolo b más el símbolo a y terminando con el símbolo b, también podemos comenzar el recorrido con cualquier cantidad de símbolo b más el símbolo a seguido de cualquier cantidad de símbolos a mas el símbolo b más el símbolo a y terminando con el símbolo b.

El recorrido termina con el símbolo b;

5. Encuentre la expresión regular válida.

Para encontrar la expresión regular de este autómata manualmente es bastante complicado así que usamos el simulador jflap:

La expresión regular es:

6. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifíquela si la convierte a la Izquierda o a la derecha. Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

GRAMATICA COMPLETA

7. Realice el árbol de Derivación de esa gramática

Árbol de derivación para la cadena aaaabab:

8. Identifique si ese árbol o gramática es ambigua o no y plasme las razones de su afirmación

No es ambigua ya que la gramatica libre de contexto tiene un solo árbol de derivación para una o barias cadenas.

9. Si el árbol de transición es demasiado grande, a su criterio seleccione una regla en la que se detenga por cualquier rama (izquierda o derecha) y plásmelo hasta ahí. (Es decir seleccione una cadena válida para este ítem).

Árbol de transición para la cadena aab:

La siguiente es una regla para detener el árbol de transiciones por la derecha:

10. Explicar el proceso de Minimización (que estados se suprimen y porque).

1: Se crean dos subconjuntos, uno formado por los estados no finales y el otro por los estados finales.

2: Aplicar a los dos subconjuntos formados en el paso anterior, las transiciones del

AFD, en este caso aplicaremos para los subconjuntos la transición “0”.

3: Se separan del subconjunto los estados de un subconjunto que al aplicarle la transición se comporta de manera diferente a los demás estados del subconjunto.

Esto es, el que se desplaza hacia el estado final en nuestro caso es q1 para los estados no finales y q4 para los estados finales.

Aquí se vuelve a repetir el paso dos y el tres y nuevamente el 2.

R. 2: Aplicar a los dos subconjuntos formados en el paso anterior, las transiciones del AFD, en este caso aplicaremos para los subconjuntos la transición “1”.

R. 3: Se separan del subconjunto los estados de un subconjunto que al aplicarle la transición se comporta de manera diferente a los demás estados del subconjunto.

Esto es, el que se desplaza hacia el estado final en nuestro caso es q0 para los estados no finales y q3 para los estados finales.

...