Colaborativo 2 Automatas

TRABAJO COLABORATIVO 2 AUTOMATAS Y LENGUAJES FORMALES

Presentado por:

GERLEIN YESITH GOMEZ BELTRAN

ROBERTO FUENTES A MARELVIS DEL CARMEN GUTIERREZ MORELOS

Tutor: JAIME JOSE VALDEZ

Grupo Colaborativo: 301405

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA “UNAD” ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍAS E INGENIERÍAS PROGRAMA DE INGENIERÍA DE SISTEMAS OCTUBRE DE 2011

TABLA DE CONTENIDO

Introducción…………………………………………………………………………… Objetivos………………………………………………………………………………. LENGUAJES INDEPENDIENTES DEL CONTEXTO……………………………. CONSTRUCCIÓN DE AUTÓMATAS……………………………………………… AUTOEVALUACIÓN……………………………………………………………….… CONCLUSIÓN………………….……………………………………………………. BIBLIOGRAFÍA……………………………………………………………………….. WEBGRAFÍA…………………………………………………………………………..

INTRODUCCIÓN

Los lenguajes regulares son la buena manera de validar campos del texto tales como nombres, las direcciones, los números de teléfono, y otra información del usuario. Podemos utilizarlas para obligar la entrada, aplicar reglas del formato, y mucho más; hay varios métodos de cómo validar información y entre ellos, se encuentran los Autómatas de Pila que contienen las expresiones regulares, que tienen parecido a una especie de lenguaje que se puede usar para buscar, remplazar y sobreponer ciertos patrones en un texto, trabajable casi de manera igual que los Autómatas Finitos y no Finitos. Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata a pila pertenece al grupo de los lenguajes de contexto libre en la clasificación de la Jerarquía de Chomsky.

OBJETIVOS

OBJETIVO GENERAL

Reconocer los lenguajes independientes del contexto y sus diversas aplicaciones.

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.

EJERCICIOS A DESARROLLAR: 1. Describa y explique cada uno de los elementos que permiten definir formalmente un Autómata a Pila (AFPD) como una 7- upla.

Un Autómata de pila es una séptupla Q: es un conjunto finito de estados. ∑: es un conjunto finito de símbolos terminales. r: es el alfabeto de la pila.

∆: es una relación de Q x (∑U {ε}) r en subconjuntos finitos de (Q x movimientos o transiciones validos del autómata.

2. Construya el Autómata a pila para el lenguaje L={anbn | n > 0} APV=({a,b},{S,A},{p,q},S,p,f, ∅) f(p,a,S)={(p,A)} f(p,a,A)={(p,AA)} f(p,b,A)={(q, λ)} f(q,b,A)={(q, λ)} • • • Grafíquelo en JFLAP y realice el “Traceback” par las transiciones. Plasme las imágenes y capturas en el documento. Trabájelo en el simulador JFLAP

r ) que define los

3. Diseñar un autómata de pila M tal que L(M) = {xn ymxn; m,n∈ N}. Trabájelo en el simulador JFLAP

APV = ({X,Y},{S,X,Y},{p,q.r},S,P,f,φ)

Estados de transición f(P,X,S)= {(P,X)} , f(P,X,X) = {(P,XX)} f(P,Y,X)= {(q,λ)} , f(q,Y,X)= {(q,λ)} f(q,Y,X)= {(q,Y)} , f(q,Y,Y)= {(q,YY)} f(q,Y,X)={(r,λ)} , f(r,X,Y) = {(r, λ)}

Diagrama de Moore

Los lenguajes aceptados por este autómata son: El número de xx vaciada en la pila debe ser igual al número de entradas de x a la pila XXXYYYXXX XXYYYYXX XXYYYXX

4. Cuál es el lenguaje aceptado por el siguiente autómata de pila? Trabájelo en el simulador JFLAP.

PROGRAMA PASADO AL SIMULADOR JFLAP

5. Construir un AFPD que reconozca:

Trabájelo en el simulador JFLAP.

6. Construir un autómata con pila que reconozca por vaciado de pila el lenguaje que contiene las palabras formadas por los símbolos “0”, “1” y “2” que tienen tantas apariciones de las secuencia “01” como del símbolo “2”. • Trabájelo en el simulador JFLAP.

AP = ({0,1,2}, {Z,A}, {q0, q1, q2}, q0, Z, f, ∅)

f(q0,0,Z) = {(q1, AZ)} f(q0,0,A) = { (q0,A),(q1, AA), (q2,λ)} f(q0,1,A) = {(q2, λ)} f(q0,2,A)

...