MATEMÁTICA
DISCRETA
Gramáticas
LENGUAJES
Los lenguajes se pueden especificar de varias formas:
• Enumerar todas las palabras que conforman el lenguaje, o
• Dar algunos criterios que una palabra debe satisfacer para pertenecer al lenguaje
Nosotros utilizaremos una «gramática» para especificar un lenguaje. Por ejemplo, el
conjunto de reglas que se dieron al inicio de la sesión.
Una gramática proporciona un conjunto de símbolos de varios tipos y un conjunto de
reglas para construir palabras.
GRAMÁTICAS - Introducción
Una gramática consta de:
• Un alfabeto 𝑉, que es el conjunto de símbolos usados para obtener los elementos
de un lenguaje.
• Símbolos terminales 𝑇 , los elementos del alfabeto que no se pueden reemplazar
por otros símbolos.
• Símbolos no terminales 𝑁, los elementos restantes del alfabeto, aquellos que
pueden sustituirse por otros símbolos.
En el ejemplo dado en la introducción:
𝑇 = 𝑢𝑛, 𝑒𝑙, 𝑐𝑜𝑛𝑒𝑗𝑜, 𝑚𝑎𝑡𝑒𝑚á𝑡𝑖𝑐𝑜, 𝑠𝑎𝑙𝑡𝑎, 𝑐𝑜𝑚𝑒, 𝑟á𝑝𝑖𝑑𝑎𝑚𝑒𝑛𝑡𝑒, 𝑠𝑎𝑙𝑣𝑎𝑗𝑒𝑚𝑒𝑛𝑡𝑒
𝑁 = {𝑓𝑟𝑎𝑠𝑒, 𝑠𝑢𝑗𝑒𝑡𝑜, 𝑝𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜, 𝑎𝑑𝑗𝑒𝑡𝑖𝑣𝑜, 𝑎𝑟𝑡í𝑐𝑢𝑙𝑜, 𝑛𝑜𝑚𝑏𝑟𝑒, 𝑣𝑒𝑟𝑏𝑜, 𝑎𝑑𝑣𝑒𝑟𝑏𝑖𝑜}
GRAMÁTICAS - Introducción
• Símbolo inicial 𝑆, en el alfabeto 𝑉 hay un elemento especial, que es un elemento
por el que siempre comenzamos.
En el ejemplo dado en la introducción, el símbolo inicial es 𝒇𝒓𝒂𝒔𝒆.
• Producción de la gramática, toda regla que especifica cuándo se puede
reemplazar una cadena de 𝑉 ∗ por otra cadena. Se denota por 𝑧0 → 𝑧1 (𝑧0 puede
reemplazarse por 𝑧1 en la cadena)
En el ejemplo dela introducción, se listaron las producciones de la gramática. La
primera producción, escrita utilizando esta notación, es
𝒇𝒓𝒂𝒔𝒆 → 𝒔𝒖𝒋𝒆𝒕𝒐 𝒑𝒓𝒆𝒅𝒊𝒄𝒂𝒅𝒐.
GRAMÁTICA
Definición 9
Una gramática con estructura de frases 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) consiste en un alfabeto 𝑉,
un subconjunto 𝑇 de 𝑉 formado por los elementos terminales, un símbolo inicial 𝑆 de
𝑉 − 𝑇 y un conjunto 𝑃 de producciones.
• El conjunto 𝑉 − 𝑇 se denota por 𝑁.
• Los elementos de 𝑁 se llaman elementos no terminales.
• Toda producción de 𝑃 debe contener al menos un elemento no terminal en su
lado izquierdo.
Ejemplo:
Sea 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃), donde 𝑉 = 𝑎, 𝑏, 𝐴, 𝐵, 𝑆 , 𝑇 = 𝑎, 𝑏 , 𝑆 es el símbolo inicial y 𝑃
= {𝑆 → 𝐴𝐵𝑎, 𝐴 → 𝐵𝐵, 𝐵 → 𝑎𝑏, 𝐴𝐵 → 𝑏}, 𝐺 es un ejemplo de gramática con estructura
de frases
GRAMÁTICA
Estamos interesados en las palabras que pueden generarse mediante las producciones
de una gramática con estructura de frases.
Definición 10
Sea 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) una gramática con estructura de frases. Sean 𝑤0 = 𝑙𝑧0 𝑟 (la
concatenación de 𝑙, 𝑧0 y 𝑟) y 𝑤1 = 𝑙𝑧1 𝑟 cadenas sobre 𝑉. Si 𝑧0 → 𝑧1 es una producción
de 𝐺, decimos que 𝑤1 se deriva directamente de 𝑤0 (o que es directamente
derivable), y escribimos 𝑤0 ⇒ 𝑤1 .
Si 𝑤0 , 𝑤1 , … , 𝑤𝑛 son cadenas sobre 𝑉 tales que 𝑤0 ⇒ 𝑤1 , 𝑤1 ⇒ 𝑤2 , … , 𝑤𝑛−1 ⇒ 𝑤𝑛 ,
decimos que 𝑤𝑛 es derivable (o se deriva) de 𝑤0 , y se denota 𝑤0 ⇒ 𝑤𝑛
La secuencia de pasos utilizada para obtener 𝑤𝑛 a partir de 𝑤0 se llama derivación.
GRAMÁTICA
Ejemplo:
• En la cadena 𝐴𝑎𝑏𝑎 se deriva directamente de 𝐴𝐵𝑎 en la gramática del ejemplo
anterior, puesto que
𝐵 → 𝑎𝑏
Es una producción de dicha gramática.
• La cadena 𝑎𝑏𝑎𝑏𝑎𝑏𝑎 se deriva de 𝐴𝐵𝑎, puesto que
𝐴𝐵𝑎 ⇒ 𝐴𝑎𝑏𝑎 ⇒ 𝐵𝐵𝑎𝑏𝑎 ⇒ 𝐵𝑎𝑏𝑎𝑏𝑎 ⇒ 𝑎𝑏𝑎𝑏𝑎𝑏𝑎
Donde se han utilizado las producciones
𝐵 → 𝑎𝑏,
𝐴 → 𝐵𝐵,
𝐵 → 𝑎𝑏
𝐵 → 𝑎𝑏
sucesivamente.
Ejercicio
GRAMÁTICA
Ejemplo:
Construye una gramática con estructura de frases que genere el conjunto {0𝑛 1𝑛 : 𝑛 =
0,1,2, … }
Solución:
Se pueden utilizar dos producciones para generar todas las cadenas de ceros seguida
del mismo número de unos, incluyendo la palabra vacía.
1º: La primera producción 2º: La segunda producción reemplaza 𝑆 por la
crece formando cadenas cadena vacía
cada vez más largas del 𝑆→𝜆
lenguaje mediante la
concatenación de un 0 al La solución es 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) , donde 𝑉
inicio de la cadena y un 1 al = 0,1, 𝑆 , 𝑇 = 0,1 , 𝑆 es el símbolo inicial y
final. las producciones son
𝑆 → 0𝑆1
𝑆 → 0𝑆1 𝑆→𝜆
GRAMÁTICA
Definición 11
Sea 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) una gramática con estructura de frases. El lenguaje generado por
𝐺 (o el lenguaje de 𝐺), denotado por 𝐿(𝐺), es el conjunto de todas las cadenas de
terminales que se derivan del estado inicial 𝑆. En otras palabras,
𝐿 𝐺 = {𝑤 ∈ 𝑇: 𝑆 ⇒ 𝑤}
Ejemplo:
Sea 𝐺 la gramática con alfabeto 𝑉 = 𝑆, 𝐴, 𝑎, 𝑏 , conjunto de terminales 𝑇 = 𝑎, 𝑏 ,
símbolo inicial 𝑆 y producciones 𝑃 = {𝑆 → 𝑎𝐴, 𝑆 → 𝑏, 𝐴 → 𝑎𝑎}, ¿Cuál es 𝐿(𝐺), el
lenguaje generado por esta gramática?
GRAMÁTICA
Ejemplo:
Sea 𝐺 la gramática con alfabeto 𝑉 = 𝑆, 𝐴, 𝑎, 𝑏 , conjunto de terminales 𝑇 = 𝑎, 𝑏 ,
símbolo inicial 𝑆 y producciones 𝑃 = {𝑆 → 𝑎𝐴, 𝑆 → 𝑏, 𝐴 → 𝑎𝑎}, ¿Cuál es 𝐿(𝐺), el
lenguaje generado por esta gramática?
Solución:
A partir del estado inicial se tiene:
1. 𝑆 → 𝑎𝐴
1º: 𝑆 ⇒ 𝑎𝐴 ⇒ 𝑎𝑎𝑎
2. 𝑆 → 𝑏
3. 𝐴 → 𝑎𝑎
2º: 𝑆 ⇒ 𝑏
Entonces: 𝐿 𝐺 = {𝑏, 𝑎𝑎𝑎}
GRAMÁTICA
Ejemplo:
Sea 𝐺, la gramática con alfabeto 𝑉 = 𝑆, 0,1 , conjunto de terminales 𝑇 = 0,1 ,
símbolo inicial 𝑆 y producciones 𝑃 = 𝑆 → 11𝑆, 𝑆 → 0 . ¿Cuál es 𝐿(𝐺), el lenguaje
generado por esta gramática?
Solución:
A partir de 𝑆
1º: 𝑆 ⇒ 0 1. 𝑆 → 11𝑆
2º: 𝑆 ⇒ 11𝑆 ⇒ 110 2. 𝑆 → 0
3º: 𝑆 ⇒ 11𝑆 ⇒ 1111𝑆 ⇒ 11110
4º: 𝑆 ⇒ 11𝑆 ⇒ 1111𝑆 ⇒ 111111𝑆 ⇒ 1111110
Entonces: 𝐿 𝐺 = {0, 110, 11110, 1111110, … }
Conjunto de todas las cadenas que comienzan con un número par de unos y
terminan con un 0.
Ejercicio
Ejercicio
8. Sean 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃), donde 𝑉 = 𝑎, 𝑏, 𝐴, 𝐵, 𝑆 , 𝑇 = 𝑎, 𝑏 , 𝑆 es el símbolo inicial. Halle
el lenguaje generado por 𝐺, siendo el conjunto de producciones:
𝑐 𝑆 → 𝐴𝐵, 𝑆 → 𝐴𝐴, 𝐴 → 𝑎𝐵, 𝐴 → 𝑎𝑏, 𝐵 → 𝑏
TIPOS DE GRAMÁTICA CON ESTRUCTURA DE FRASES
Las gramáticas con estructura de frases se pueden clasificar de acuerdo con el tipo de
producciones que utilicen
Tipos
Consideremos la producción 𝑤1 → 𝑤2
Tipo 0: no impone restricción a sus producciones
Tipo 1: 𝑙𝑜𝑛𝑔 𝑤1 < 𝑙𝑜𝑛𝑔(𝑤2 ), o 𝑤2 = 𝜆
Tipo 2: 𝑤1 = 𝐴, siendo 𝐴 un símbolo no terminal
Tipo 3: 𝑤1 = 𝐴 y 𝑤2 = 𝑎𝐵 o 𝑤2 = 𝑎, siendo 𝐴 y 𝐵 símbolos no terminales y 𝑎 un
símbolo terminal o 𝑤1 = 𝑆 y 𝑤2 = 𝜆
Observar!!!
Toda gramática de tipo 3 es de tipo 2,
toda gramática de tipo 2 es de tipo 1 y
toda gramática de tipo 1 es de tipo 0
TIPOS DE GRAMÁTICA CON ESTRUCTURA DE FRASES 𝒘𝟏 → 𝒘𝟐
Tipo 0 – Estructura de frase
no impone restricción a sus producciones
Tipo 1 – Dependiente del contexto
(sensible al contexto) 𝑙𝑜𝑛𝑔 𝑤1 < 𝑙𝑜𝑛𝑔(𝑤2 ), o 𝑤2 = 𝜆
Tipo 2 – Independiente del contexto
(libre de contexto) 𝑤1 = 𝐴, siendo 𝐴 un símbolo no terminal
Tipo 3 – Regular
𝑤1 = 𝐴 y 𝑤2 = 𝑎𝐵 o 𝑤2 = 𝑎, siendo 𝐴 y 𝐵 símbolos no terminales y 𝑎 un símbolo terminal o
𝑤1 = 𝑆 y 𝑤2 = 𝜆
TIPOS DE GRAMÁTICA CON ESTRUCTURA DE FRASES
Tipos
Consideremos la producción 𝑤1 → 𝑤2
Tipo 0: no impone restricción a sus producciones
Tipo 1: 𝑙𝑜𝑛𝑔 𝑤1 < 𝑙𝑜𝑛𝑔(𝑤2 ), o 𝑤2 = 𝜆
Tipo 2: 𝑤1 = 𝐴, siendo 𝐴 un símbolo no terminal
Tipo 3: 𝑤1 = 𝐴 y 𝑤2 = 𝑎𝐵 o 𝑤2 = 𝑎, siendo 𝐴 y 𝐵 símbolos no terminales y 𝑎 un
símbolo terminal o 𝑤1 = 𝑆 y 𝑤2 = 𝜆
Ejemplo
𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) , donde 𝑉 = 0,1, 𝑆 , 𝑇
= 0,1 , 𝑆 es el símbolo inicial y las Es una gramática de Tipo 2 –
producciones son Independiente del contexto
𝑆 → 0𝑆1 (libre de contexto)
𝑆→𝜆
ÁRBOLES DE DERIVACIÓN
Una derivación en el lenguaje generado por una gramática libre de contexto se puede
representar gráficamente mediante un árbol con raíz ordenado, denominado árbol de
derivación.
• La raíz del árbol representa al símbolo inicial.
• Los vértices internos representan los símbolos no terminales .
• Las hojas representan los símbolos terminales.
Observación: Si la producción 𝐴 → 𝑤 se utiliza en la derivación, donde 𝑤 es una
palabra, el vértice que representa a 𝐴 tiene como hijos en el árbol a todos los
vértices que representan a los símbolos de 𝑤 , ordenados de izquierda a
derecha.
ÁRBOLES DE DERIVACIÓN
Ejemplo
Sea 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃) ,
donde 𝑉 = 𝑎, 𝑏, 𝐴, 𝑆 , 𝑆
𝑇 = 𝑎, 𝑏 , 𝑆 es el símbolo
inicial y las producciones
son 𝑎 𝐴 𝑆
𝑆 → 𝑎𝐴𝑆|𝑎
𝐴 → 𝑆𝑏𝐴|𝑆𝑆|𝑏𝑎 𝑆 𝑏 𝐴 𝑎
Construye el árbol de 𝑎 𝑏 𝑎
derivación para la
cadena (derivación)
𝑎𝑎𝑏𝑏𝑎𝑎
ÁRBOLES DE DERIVACIÓN
Ejemplo
Construye un árbol de derivación para la derivación:
El conejo hambriento come rápidamente
frase
sujeto predicado
artículo nombre adjetivo verbo adverbio
el conejo hambriento come rápidamente
Ejercicio
12. Sea 𝐺 la gramática con 𝑉 = 𝑎, 𝑏, 𝑐, 𝑆 , 𝑇 = 𝑎, 𝑏, 𝑐 , 𝑆 es el símbolo inicial y las
producciones son 𝑆 → 𝑎𝑏𝑆, 𝑆 → 𝑏𝑐𝑆, 𝑆 → 𝑏𝑏𝑆, 𝑆 → 𝑎, 𝑆 → 𝑐𝑏. Construye los árboles
de derivación de
(a)𝑏𝑐𝑏𝑏𝑎