control de lectura_capitulo 5 - 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 
5.- Lenguajes y gramáticas independientes del contexto
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
5.- Lenguajes y gramáticas independientes del contexto 
Ideas principales.
· Entender cómo funcionan los palíndromos, así como sus reglas
· Aprender a diseñar gramáticas independientes.
· Aprender a construir arboles de derivacion
Resumen.
Estos lenguajes utilizan una notación natural recursiva: las “grama-ticas independientes del contexto”. Estas gramáticas han desarrollado un importante papel en la tecnología de compiladores desde los años sesenta; han hecho que la implementación de analizadores sintácticos (funciones que descubren la estructura de un programa) pase de ser una tarea de implementación ad-hoc y que consume mucho tiempo a ser un trabajo rutinario que puede llevarse a cabo en muy poco tiempo. Más recientemente, las gramáticas independientes del contexto se han utilizado para describir formatos de documentos a través de la denominada definición de tipo de documento (DTD,document-type definition), que utiliza la comunidad XML(eXtensible Markup Language) para el intercambio de información en la Web.
Existe una notación similar a la de los autómatas, denominada “autómata a pila”, que también describe todos sólo los lenguajes independientes del contexto
Gramáticas independientes del contexto
Definimos formalmente una gramática y presentamos el proceso de “derivación” mediante el que se determina qué cadenas pertenecen al lenguaje de la gramática.
Consideremos el lenguaje de los palíndromos. Un palíndromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda, como por ejemplo,ottoodabalearrozalazorraelabad(“Dábalearroz a la zorra el abad”). Dicho de otra manera, la cadena es un palíndromo si y sólo siw=wR. Para hacerlas cosas sencillas, consideremos únicamente los palíndromos descritos con el alfabeto{0,1}. Este lenguaje incluye cadenas del tipo 0110, 11011 yε, pero no cadenas como 011 o 0101.
PASO INDUCTIVO: Si w es un palíndromo, también lo son 0w0y1w1. Ninguna cadena es un palíndromo de ceros y unos, a menos que cumpla el caso base y esta regla de inducción.
Una gramática independiente del contexto es una notación formal que sirve para expresar las definiciones recursivas de los lenguajes. Una gramática consta de una o más variables que representan las clases de cadenas, es decir, los lenguajes.
Existen cuatro componentes importantes en una descripción gramatical de un lenguaje:
1. Un conjunto finito de símbolos que forma las cadenas del lenguaje que se está definiendo. Este conjunto era{0,1}en el ejemplo de los palíndromos que acabamos de ver. Denominamos a este conjunto alfabeto terminal alfabeto de símbolos terminales.
2. Un conjunto finito de variables, denominado también en ocasiones símbolos no terminal es o categorías sintácticas. Cada variable representa un lenguaje; es decir, un conjunto de cadenas. En el ejemplo anterior, sólo había una variable, P, que hemos empleado para representarla clase de palíndromos del alfabeto{0,1}.
3. Una de las variables representa el lenguaje que se está definiendo; se denomina símbolo inicial. Otras variables representan las clases auxiliares de cadenas que se emplean para definir el lenguaje del símbolo inicial. En el ejemplo anterior, la única variable, P, también es el símbolo inicial.
4. Un conjunto finito de producciones o reglas que representan la definición recursiva de un lenguaje. Cadena producción consta de:
a) Una variable a la que define (parcialmente) la producción. Esta variable a menudo se denomina cabeza de la producción.
b) El símbolo de producción→.
c) Una cadena formada por cero o más símbolos terminales y variables. Esta cadena, denominada cuerpo de la producción, representa una manera de formar cadenas pertenecientes al lenguaje de la variable de la cabeza. De este modo, dejamos los símbolos terminales invariables y sustituimos cada una de las variables del cuerpo por una cadena que sabemos que pertenece al lenguaje de dicha variable.
Síntesis
Tenemos que estos lenguajes ocupan una notación natural recursiva, este tipo de gramitas ha desarrollado un importante papel en la tecnología de compiladores.
Al considerar el lenguaje de los palíndromos, sabemos que un palíndromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda, Como, por ejemplo: utilizando el alfabeto {0,1}. Este lenguaje incluye cadenas del tipo 0110,11011 y épsilon, pero no cadenas como 011 o 0101.
Existe una definición recursiva y natural y esta nos dice que cuando una cadena de ceros y unos pertenece a Lpal ,Se parte de un caso básico estableciendo que unas cuantas cadenas obvias pertenecen a Lpal, y luego se aplica la idea de que si una cadena es un palíndromo, tiene que comenzar y terminar con el mismo símbolo. Además, cuando el primer y último símbolos se eliminan, la cadena resultante también tiene que ser un palíndromo.
Las reglas que definen los palíndromos expresadas empleando la notación de la gramática independiente del contexto.
Las tres primeras reglas definen el caso básico.
Las dos últimas reglas forman la parte inductiva de la definición.
1.P→ε
2.P→0
3.P→1
4.P→0P0
5.P→1P1
Las derivaciones a partir del símbolo inicial producen cadenas que desempeñan un papel especial y se conocen como “formas senténciales”
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