Automatas

AUTOMATAS Y LENGUAJES FORMALES TRABAJO COLABORATIVO 2

JENNY PAOLA HUERTAS SOLER Cód. 1056769602 Grupo: 301405_30

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA FACULTAD DE CIENCIAS BÁSICAS E INGENIERÍA U. N. A. D SOGAMOSO 2010

AUTOMATAS Y LENGUAJES FORMALES TRABAJO COLABORATIVO 2

JENNY PAOLA HUERTAS SOLER Cód. 1056769602 Grupo: 301405_30

ING. JAIRO RIAÑO TUTOR

UNIVERSIDAD NACIONALABIERTA Y A DISTANCIA FACULTAD DE CIENCIAS BÁSICAS E INGENIERÍA U. N. A. D SOGAMOSO 2010

TEMAS 1.- Un Autómata a Pila define los Lenguajes Independientes del Contexto y es una extensión de los Autómatas Finitos Deterministas con transiciones ε. Sustente suficientemente porque se afirma lo anterior. 2.- En los Autómatas Finitos, para deducir si una cadena o palabra formada con símbolos de unAlfabeto es aceptada o no, se deduce luego de consumir toda la cadena y revisar si el estado en que quedo el autómata pertenece al conjunto de estados de aceptación o no. Describa detalladamente como es el proceso análogo en un Autómata a Pila. 3.- Describa y explique cada uno de los elementos que permiten definir formalmente un Autómata a Pila. 4.- Para el siguiente Autómata a Pila: (a). Diseñe elDiagrama de Moore (b). Que lenguaje reconoce (c). Cuales de las siguientes palabras son aceptadas por el autómata: aabbc, abbc, bbcc, aabbbcc (mostrando la sucesión de descripciones instantaneas) AP = ({a, b, c}, {A, B, S}, {q, r, s, t}, q, S, f, O) f(q, a, S) = {(r, S)} f(s, b, S) = {(s, BS)} f(q, a, A) = {(r, A)} f(s, b, A) = {(s, λ)} f(q, b, S) = {(s, BS)} f(s, b, B) = {(s, BB)} f(q, b, A) ={(s, λ)} f(s, c, B) = {(t, λ)} f(r, a, S) = {(q, AS)} f(t, c, B) = {(t, λ)} f(r, a, A) = {(q, AA)} f(t, λ, S) = {(t, λ)} 5.- Definir formalmente el lenguaje reconocido por el siguiente autómata con pila: A = ({a,b,c}, {S,A,B}, {q,r,s,p}, q, S, f, Æ) f(q, a, S) = {(r, S)} f(s, b, S) = {(s, BS)} f(q, b, S) = {(s, BS)} f(s, b, A) = {(s, λ)} f(q, a, A) = {(r, A)} f(s, b, B) = {(s, BB)} f(q, b, A) = {(s,λ)} f(s, c, B) = {(p, λ)} f(r, a, S) = {(q, AS)} f(p, c, B) = {(p, λ)} f(r, a, A) = {(q, AA)} f(p, λ, S) = {(p, λ)}

6.- Dado el siguiente autómata con pila indicar: (a) Que lenguaje reconoce por vaciado de pila. (b) Cuales de las siguientes palabras son aceptadas por el AP: abba, abaaba. AP = ({a,b}, {Z}, {q0, q1, q2, q3}, q0, Z, f, Æ) f(q0, a, Z) = {(q1, aZ)} f(q2, b, b) = {(q2, λ)} f(q0, b,Z) = {(q1, bZ)} f(q2, a, a) = {(q2, λ)} f(q1, a, a) = {(q1, aa), (q2, λ)} f(q2, λ, Z) = {(q2, λ)} f(q1, a, b) = {(q1, ab)} f(q1, b, a) = {(q1, ba)} f(q1, b, b) = {(q1, bb), (q2, λ)} CONSTRUCCIÓN DE AUTÓMATAS 7.- Construir un autómata con pila que reconozca cada uno de los siguientes Lenguajes: (a) L = { anb2n/ n > 0 } (b) L = { anbmcn/ n, m > 0 } (c) L = { x / x Î {0,1}+ & no 0´s = no 1´s } (d) L= { aibjci+j / i, j > 0 } (e) L = { a2ib3i / i >= 0 } 8.- 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”. 9.- Dado el siguiente lenguaje: L = { anbcmdmen / n, m > 0 } (a)Construir un autómata con pila que reconozca dicho lenguajepor vaciado de pila. (b)Comprobar mediante el uso de descripciones instantáneas que la cadena “aabccddee” es aceptada por dicho autómata. 10.- Construir un autómata con pila que reconozca por vaciado de pila el lenguaje siguiente: L = { 0n1n / n > 0 } È { 0n12n / n > 0 }

DESARROLLO

Un Autómata a Pila define los Lenguajes Independientes del Contexto y es una extensión de los AutómatasFinitos Deterministas con transiciones ε. Autómatas a Pila 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. AFND Un autómata finito...