CURSO ACADEMICO: AUTOMATAS Y LENGUAJES FORMALES

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

...