control de lectura_capitulo 7 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
7.- Propiedades de los lenguajes independientes del contexto
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
7.- Propiedades de los lenguajes independientes del contexto
Resumen.
El objetivo de esta sección es demostrar que todo LIC (sinε) es generado por una GIC en la que todas las producciones son de la forma A→B C o A→ a, donde A, B y C son variables ya es un símbolo terminal.
Esta forma se conoce como forma normal de Chomsky. Para llegar a ella, tenemos que hacer una serie de simplificaciones preliminares, que por sí mismas resultan útiles en diversos contextos:1. Tenemos que eliminar los símbolos inútiles, aquellas variables o símbolos terminales que no aparecen en ninguna derivación de una cadena terminal que parta del símbolo inicial.2. Tenemos que eliminar las producciones-ε, aquellas de la forma A→ ε para alguna variableA.3. Tenemos que eliminar la Producción unitaria, aquellas de la forma A→B para A y B.
Eliminación de símbolos inútiles Decimos que un símbolo X es útil para una gramática G=(V,T,P,S)si existe alguna derivación de la forma S⇒∗αXβ⇒∗w, donde w pertenece a T∗. Observe que X puede ser V o T, y la forma sentencia α X β puede ser la primera o la última en la derivación. Si X no es útil, decimos que es inútil. Evidentemente, la omisión delos símbolos inútiles de una gramática no cambiará el lenguaje generado, por lo que podemos también detectar y eliminar todos los símbolos inútiles. El método para eliminar los símbolos inútiles identifica en primer lugar las dos cosas que un símbolo tiene que cumplir para resultar útil:1. Decimos que X es generador si X⇒∗w para alguna cadena terminal w. Observe que todo símbolo terminal generador, ya que w puede ser ese mismo símbolo terminal, el cual se obtiene en cero pasos.2. Decimos que X es alcanzable si existe una derivación S⇒∗α X β para algúnα y β. Sin duda, un símbolo que es útil será generador y alcanzable. Si eliminamos los símbolos que no son generadores en primer lugar y luego eliminamos de la gramática resultante aquellos símbolos que no son alcanzables, tendremos sólo los símbolos útiles
 Eliminación de producciones-ε
Ahora vamos a demostrar que las producciones-ε, aunque sean convenientes en muchos problemas de diseño de gramáticas, no son esenciales. Por supuesto, sin una producción que tenga un cuerpo ε, es imposible generarla cadena vacía como miembro del lenguaje. Por tanto, lo que realmente vamos a demostrar es que si el lenguaje L tiene una GIC, entonces L−{ε}tiene una GIC sin producciones-ε.Si εn o pertenece a L, entonces el propio L esL−{ε}, por lo que L tiene una GIC sin producciones-ε.La estrategia que vamos a seguir es comenzar por descubrir qué variables son “anulables”. Una variable A es anulable si A⇒∗ε. Si A es anulable, entonces cuando A aparece en el cuerpo de una producción, decimos que B→ CAD, A puede (o no) generar ε. Construimos dos versiones de la producción, una sin A en el cuerpo(B→CD), que corresponde al caso en que A tendría que haberse empleado para generar ε, y el otro en el que A ya está presente en (B→CAD). Sin embargo, si utilizamos la versión en la que aparece A, entonces no podemos permitir que A genere ε. Esto no es un problema, ya que simplemente eliminaremos todas las producciones cuyo cuerpo sea ε, evitando así que alguna variable genere ε. Sea G=(V,T,P,S)una GIC. Podemos encontrar todos los símbolos anulables de G mediante el siguiente algoritmo iterativo. Demostraremos entonces que no existen más símbolos anulables que los que el algoritmo encuentra. BASE.Si A→ε es una producción de G, entonces A es anulable. PASO INDUCTIVO. Si existe una producciónB→C1C2···Ck, donde cadaCies anulable, entonces B es anulable. Observe que cada C tiene que ser una variable anulable, por lo que sólo hay que considerar las producciones cuyos cuerpos sean sólo variables.
Bibliografías.
2008 por PEARSON EDUCACIÓN S.A.Ribera del Loira, 2828042 Madrid
Introducción a la teoría de autómatas, lenguajes y computaciónHopcroft, J. E.; Motwani, R.; Ullman, J. D.
Página 1 | 1
Acapulco Gro. 30 de octubre de 2020