Segunda Lista de ejercicios referentes a Lenguajes y Gramáticas
Ejercicio 1
Dados los siguientes lenguajes formales definidos sobre el alfabeto ∑= {a, b}:
• L0={}
• L1={ε}
• L2={a}
• L3={a,b}
• L4={(ab)n | 0<= n < 2 }
• L5={ambl | m,l >= 0 }
• L6={anbn | n>=0 }
• L7 ={lenguaje formado por las palabras que tienen un número impar de aes}
Determinar para cada uno de ellos L0, L3 y L*
Ejercicio 2
Sean las siguientes operaciones con los anteriores lenguajes formales:
L0n L1n, L0n| L1n, L 0n |L0n, L3n L1n, L3n | L1n, L3n L0n, L3n| L0n, L7n ∩ L5n, L 7 n|
L5n
1. Determinar qué lenguajes definen suponiendo que n = 0.
2. Determinar qué lenguajes definen suponiendo que n = 3
3. Determinar qué lenguajes definen suponiendo que n = *
Ejercicio 3
Obtener una gramática para cada uno de los siguientes lenguajes:
1. ∑ = {a, b, c}, L = {an bm cn | n, m >= 1}
2. ∑ = {a, b, c}, L = {an bm cn+2m | n >=0, m >= 1}
3. ∑ = {a, b, c}, L = {an bn+m cm | n >= 1, m >= 0}
4. ∑ = {a, b}, L = {an bm | n >= m >= 1}
5. ∑ = {a, b}, L = {an bm | n > m >= 0}
6. ∑ = {a, b, c}, L = {am bn ck | m > n + k ; n, k >=0}
7. ∑ = {a, b}, L = { anbm | m <= n <= 2m ; n, m >=0}
8. ∑ = {a, b}, L = { anbm | n <>m ; n, m >0}
Ejercicio 4
Construir una gramática que especifique el siguiente lenguaje:
L = { w ∈ {0, 1, 2}* | w contiene exactamente dos o tres símbolos 0 en cualquier posición}.
¿Sería posible obtener una gramática regular o de tipo 3?
Ejercicio 5
Dado el alfabeto Σ= {a, +, = } y el siguiente lenguaje: L={an+am=an+m | n, m > 0}, construir
una gramática de tipo 2 que defina dicho lenguaje.
Pág 1
Ejercicio 6
Para el alfabeto Σ = {a, b, c} construir una gramática que genere el lenguaje L cuyas palabras
cumplen las siguientes condiciones:
• Empiezan y terminan por a.
• Entre los dos símbolos a sólo hay símbolos b y c, con la peculiaridad de que deben
aparecer de forma alterna y en cuantía indeterminada (de cero a infinito). Además, esta
subcadena de símbolos b y c alternos puede empezar por cualquiera de los dos y puede
tener longitud par o impar.
Ejercicio 7
Sea el lenguaje de sumas de números naturales sobre Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, + }.
Ejemplos de palabras del lenguaje: 2+67+9870 ó 35
Ejemplos de palabras no válidas: 34+ ó 34++23
Representar mediante una gramática de tipo 2 en notación BNF los siguientes lenguajes.
1. Sea L1 el lenguaje de sumas en el que los números naturales no pueden tener ceros a la
izquierda. El número 0 se representará por un único cero, nunca por una secuencia de
ceros.
Ejemplo:10+0
Ejemplo de palabra no válida: 03+12
2. Sea L2 el lenguaje de sumas en el que los números naturales pueden empezar por 0, aunque
no sea el número 0, pero en cada suma se cumple siempre la condición de que el primer y el
último número tienen siempre la misma longitud (al menos habrá dos números).
Ejemplo: 10+1+01
Ejemplos de palabras no válidas: 03+129 , 1
3. Sea L3 el lenguaje de sumas en el que los números naturales pueden empezar por 0, aunque
no sea el número 0, pero en el que se cumple la condición de que al menos dos números
tienen la misma longitud.
Ejemplo: 0503+30+450+89+203+03
Ejercicio 8
Para las gramáticas que se proponen a continuación, determinar el tipo de las mismas y el
lenguaje generado.
1. S → 0S | A
A → 0B | 0
B → 1A
2. S→ abA | bbB
A → bC
B→a
C → cS | ε
3. S → 0A
A → 0A | 1S | 0
Ejercicio 9
Pág 2
Dada la siguiente gramática:
S ---> aAa
Aa ---> bAa | ba
Determinar de forma justificada el tipo de la misma y el tipo del lenguaje generado.
Ejercicio 10
Sea la siguiente gramática definida sobre el alfabeto ∑ = {a, +, = }
S → BSa | aSa | a+a=aa
Ba → aB
B+ → +a
Obtener el lenguaje generado por la misma
Ejercicio 11
Sea la siguiente gramática:
S → aSc | A
A → bBA | ε
Bb → bB
Bc → ε
Determinar el lenguaje generado por la misma, expresándolo en notación matemática o de
potencias.
Ejercicio 12
La siguiente gramática genera el lenguaje L = {an bn cn | n>=1}
S → aASc | abc
Aa → aA
Ab → bb
1. Modificarla para que genere el lenguaje L = {an bn cn | n>=0}.
2. Modificarla para que genere el lenguaje L = {an b2n cn | n>=1}.
Pág 3
