Automatas
Páginas: 3 (722 palabras)
Publicado: 16 de mayo de 2013
RELACIÓN ENTRE AUTOMATAS DE PILA Y UNA GRAMATICA INDEPENDIENTE DEL CONTEXTO
OBJETIVO
Analizar la relación que existe entre los autómatas de pila y las gramáticas independientes del contexto,así como su construcción a partir de las gramáticas.
JUSTIFICACIÓN
La relación que existe entre los AP y las GLC es un factor importante, ya que por medio de una GLC podemos desarrollar un AP.INTRODUCCIÓN
Los autómatas de pila (AP) son autómatas utilizados para representar GLC. Para ello utilizan símbolos de entrada y salida que van usando la pila, tratando de que al final se llegue ala pila vacía, es decir, que se reconozca el lenguaje.
CONTENIDO
En ocasiones será conveniente considerar transiciones únicas que insertan mas de un símbolo en la pila, como (p,a,S;q,xyz).En este caso se insertan en la pila de símbolos z, y, x (en ese orden). Así después de efectuar la transición, x se hallara en la cima (con y debajo y z en el fondo).
A continuación mostraremosque los lenguajes generados por gramáticas independientes del contexto son exactamente los mismos lenguajes que aceptan los autómatas de pila. Primero se vera que para cualquier gramática Gindependiente del contexto existe un autómata de pila M tal que L(M)=L(G) (teorema 2.2) luego para cualquier autómata de pila existe una gramática G independiente del contexto tal que L(G)=L(M) (T. 2.3)TEOREMA 2.2
Para cada gramática G independiente del contexto, existe un autómata de pila M tal que L(G)=L(M).
Demostración
Dada una gramática G independiente del contexto, construimos unautómata de pila M de la manera siguiente:
1. Designe el alfabeto de M como los símbolos terminales de G, y los símbolos de pila de M como los símbolos terminales y no terminales de G, junto con #(suponiendo que # no es un símbolo terminal o no terminal a G)
2. Designe los estados de M como i, p, q y f. Donde i es el estado inicial y f es el único estado de aceptación.
3. Introduzca la...
OBJETIVO
Analizar la relación que existe entre los autómatas de pila y las gramáticas independientes del contexto,así como su construcción a partir de las gramáticas.
JUSTIFICACIÓN
La relación que existe entre los AP y las GLC es un factor importante, ya que por medio de una GLC podemos desarrollar un AP.INTRODUCCIÓN
Los autómatas de pila (AP) son autómatas utilizados para representar GLC. Para ello utilizan símbolos de entrada y salida que van usando la pila, tratando de que al final se llegue ala pila vacía, es decir, que se reconozca el lenguaje.
CONTENIDO
En ocasiones será conveniente considerar transiciones únicas que insertan mas de un símbolo en la pila, como (p,a,S;q,xyz).En este caso se insertan en la pila de símbolos z, y, x (en ese orden). Así después de efectuar la transición, x se hallara en la cima (con y debajo y z en el fondo).
A continuación mostraremosque los lenguajes generados por gramáticas independientes del contexto son exactamente los mismos lenguajes que aceptan los autómatas de pila. Primero se vera que para cualquier gramática Gindependiente del contexto existe un autómata de pila M tal que L(M)=L(G) (teorema 2.2) luego para cualquier autómata de pila existe una gramática G independiente del contexto tal que L(G)=L(M) (T. 2.3)TEOREMA 2.2
Para cada gramática G independiente del contexto, existe un autómata de pila M tal que L(G)=L(M).
Demostración
Dada una gramática G independiente del contexto, construimos unautómata de pila M de la manera siguiente:
1. Designe el alfabeto de M como los símbolos terminales de G, y los símbolos de pila de M como los símbolos terminales y no terminales de G, junto con #(suponiendo que # no es un símbolo terminal o no terminal a G)
2. Designe los estados de M como i, p, q y f. Donde i es el estado inicial y f es el único estado de aceptación.
3. Introduzca la...
Leer documento completo
Regístrate para leer el documento completo.