CURSO ACADEMICO: AUTOMATAS Y LENGUAJES FORMALES
Enviado por serrato7 • 31 de Octubre de 2013 • 1.807 Palabras (8 Páginas) • 481 Visitas
TRABAJO COLABORATIVO N° 2
DIANIS VELASQUEZ VELASQUEZ YEIDER MANUEL VELASQUEZ VELASQUEZ
CODIGO: 1072254003
E – mail: ymvelasquezv@unadvirtual.edu.co
GRUPO: 301405_63
TUTOR: JESUS EMIRO VEGA
CURSO ACADEMICO: AUTOMATAS Y LENGUAJES FORMALES
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA “UNAD” ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA – ECBTI
CERES BAJO SINU- CCAV SAHAGUN CORDOBA MAYO DEL 2013
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD www.unad.edu.co
INTRODUCCION.
El siguiente trabajo corresponde al desarrollo del trabajo colaborativo del curso de Autómatas y lenguajes formales, en el aplicaremos los contenidos temáticos que hemos adquirido del estudio de la unidad dos.
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.
Es factible producir de esta manera todos los lenguajes regulares, además de que existen ejemplos sencillos de gramáticas de contexto libre que generan lenguajes no regulares. Las reglas gramaticales de este tipo permiten que la sintaxis tenga variedad y refinamientos mayores que los realizados con lenguajes regulares, en gran medida sirven para especificar la sintaxis de lenguajes de alto nivel y otros lenguajes formales.
OBJETIVO GENERAL.
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.
Generalizar los conceptos de autómatas finitos y gramáticos regulares.
Reconocer el potencial de procesamiento del lenguaje del autómata con los Autómatas de pila.
EJERCICIOS A DESARROLLAR.
1. Calcular el autómata mínimo correspondiente al siguiente autómata finito determinista.
ACTIVIDADES ANTES DE MINIMIZAR
1. Identifique los componentes del autómata (que tipo de tupla es).
R/ El autómata es AFD por lo tanto la tupla es:
Q es un conjunto de estados.
Σ es el alfabeto de entrada
: Q X Σ → Q es la función (total) de transición. Dados un estado y una entrada devuelve un estado.
q0 € Q es el estado inicial
F Q es el conjunto de estados finales o de aceptación.
Acepta las cadenas como:
2. Identifique la tabla de transición. R/
a B
#q0 { q2 } { q4 }
q1 { q1 } { q0 }
#q2 { q2 } { q5 }
q3 {q3 } { q2 }
q4 { q5 } { q1 }
q5 { q4 } {q3 }
3. Identifique el lenguaje que reconoce y las posibles cadenas.
Posibles cadenas aaabbbaaa aabbbaa
abbba bbbaaa
aaa abbbaaaa aaabbbaa abbbaa
4. Encuentre la expresión regular válida (compruebe una cadena válida de esa Expresión regular en el simulador).
R/La expresión regular válida es: a(a+ba*ba*b)*+b(aa*b)*ba*ba*+ a(a+ba*ba*b)*+b(aa*b)*ba*ba*
Expresión en el simulador.
Cadenas validas en el simulador.
5. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifique si al concierte a la derecha o a la izquierda. Plásmela en el simulador y recréela.
R/ La gramática válida para la función de transición es:
La conversión al realizamos a la derecha ya que todas las producciones son de la forma:
En el lado derecho de las producciones el símbolo no terminal aparece a la derecha del símbolo terminal.
Gramática en el simulador.
En el simulador seleccionamos gramática
Ingresamos la gramática en el simulador.
Comprobamos si las cadenas son aceptadas o no para ello seleccionamos input y luego seleccionamos MultipleBrute Force Parse e ingresamos las cadenas y comprobamos.
6. Realice el árbol de derivación de esa gramática.
R/ El árbol es demasiado grande solo se colocó las gramáticas
S
B D
a
a E b A
b D b S a C
a C b
b
B a b
b
7. Identifique si ese árbol o gramática es ambigua o no y plasme las razones de su Afirmación.
R/ La gramática del árbol no es ambigua debido a que es una gramática de libre contexto y tiene asociado un solo árbol; lo contario de la ambigua que hay dos o más árboles de derivación distintos para una misma cadena.
La cadena abbba el único árbol que la puede representar es el siguiente:
8. 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í.
R/
La siguiente es la regla para detener el árbol por
...