Trabajo Colaborativo 2 Automatas Y Lenguajes Formales
Enviado por rilegran24 • 5 de Diciembre de 2013 • 1.502 Palabras (7 Páginas) • 1.501 Visitas
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.
...