EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

EJERCICIOS del TEMA 3: Lenguajes independientes del contexto

Sobre GICs (gramáticas independientes del contexto)

1. Sea G una gramática con las siguientes producciones:

S → ASB | ε
A → aAb | ε
B → bBa | ba
a) Da una derivación a la izquierda de la palabra aabbba.
b) Da una derivación a la derecha de la misma palabra del apartado (a).
c) Da una derivación que no sea ni a la derecha ni a la izquierda de la misma
palabra del apartado (a).
d) Describe L(G).

2. Sea G una gramática independiente del contexto cuyo conjunto de reglas es el

siguiente:
S → ASB | ε
A → aA | ε
B → bB | ε
a) Da una derivación a la izquierda y una derivación a la derecha de la
palabra aaabb.
b) Construye el árbol de derivación de alguna de las derivaciones anteriores.
c) Demuestra que G es ambigua.
d) Construye una gramática no ambigua equivalente a G.
e) Describe L(G). ¿Es regular este lenguaje?

3. ¿Qué lenguaje genera una gramática G = (N, Σ, S, P) donde N = {S, A}

Σ = { a, b, c, d } y P es cada uno de los conjuntos siguientes?
a) S → aaSA | ε b) S → aS | bS | A
A → bA | b A → cA | c | S

c) S → aSbb | A d) S → abSdc | c
A → cA | c A → cdAba | ε

pág. 1
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

4. Sea G = (N, Σ, S, P) donde N = { S }, Σ = { a, b } y P = { S → aSb | aSa | bSb |

bSa | ε }. Demuestra que L(G) es un lenguaje regular.

5. Demuestra que los siguientes lenguajes son independientes del contexto

buscando gramáticas de tipo adecuado que los generen.
a) { aibj : i, j ≥ 1, i ≠ j } b ) { aibicjdj : i, j ≥ 1 }
c) { aibjcjdi : i, j ≥ 1 } d ) { aibjck : i, j ≥ 1, i ≠ j ∨ j ≠k }
e) { aibjck : i, j ≥ 1, i = j ∨ j = k} f ) { aibjc2j+i : i, j ≥ 1 }
g) { aibjck : j > i+k} h ) {w ∈ {a, b}* : |w|a + 1 = |w|b }
i) { w ∈ L( a*b*a*b*): |w|a = |w|b}
j) { w ∈ {a, b}* : w contiene al menos un prefijo con más b's que a's }
k ) { xcy: x, y ∈ {a, b}* ∧ xR es subpalabra de y }
l ) { uawb: u, w ∈ {a, b}* ∧ |u| = |w| }
m ) { w1cw2c…cwkccwjR: k ≥ 1, k ≥ j ≥ 1, wi ∈ {a, b}+ para i = 1..k }
n ) {anbmcm+n: n‚ m ≥ 0}

6. (Ejercicio especial) Construye una gramática independiente del contexto que

genere cada uno de los siguientes lenguajes:
6.1 expresiones regulares sobre el alfabeto {a‚ b}
6.2 listas de palabras sobre el alfabeto {a‚ b}, por ejemplo (aa, bab, aaba)

7. Sea G = (N, Σ, S, P) la gramática cuyas reglas de producción son:

S → AB
A → aAb | aA | ε
B → Bb | ε
a) Describe el lenguaje generado por dicha gramática.
b) Esta gramática es ambigua. ¿Por qué?
c) Encuentra otra gramática no ambigua equivalente.

8. Dados los lenguajes L1 = {anbncm: n, m ≥ 0} y L2 = {anbmcm: n, m ≥ 0}:

a) Construye una gramática G1 que genere el lenguaje L1 y otra G2 que

genere el lenguaje L2.
b) A partir de esas dos gramáticas construye una gramática G que genere el
lenguaje L1 ∪ L2.
c) Prueba que G es ambigua.
d) ¿Cómo sabemos que lo era antes incluso de construirla?

pág. 2
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

9. (Ejercicio especial) Dado el lenguaje L = { x•y : x, y ∈ {a,b}* ∧ |x| = |y|

∧ x ≠ y }. Encuentra una gramática independiente del contexto que lo genere,
explicando adecuadamente su construcción.

Indicación: Para que una palabra de longitud par sea del lenguaje, sus dos
mitades x e y deben ser distintas al menos en un símbolo. Concentra tus
esfuerzos en asegurar la existencia de ese símbolo diferenciador.

10. Dada la gramática que genera un lenguaje sobre el alfabeto {a, e, if, then, else}
y cuyas producciones son las siguientes
S → a | if e then S | if e then S else S
a) Demuestra que es ambigua
b) Da una gramática equivalente no ambigua que respete el convenio
habitual en lenguajes de programación, es decir, que haga corresponder
cada else con el if más cercano.

11. (Ejercicio especial) Dadas dos gramáticas sobre el alfabeto { ( , ) , [ , ] , a } con

reglas:
i) S → a | ( S ) | SS
ii) S → a | ( S ) | [ S ] | SS
a) Demuestra que son ambiguas
b) Da dos gramáticas equivalentes no ambiguas.

12. Demuestra que ningún lenguaje regular es ambiguo.

Sobre APs (autómatas con pila)

13. Considera el autómata con pila M = (Q, Σ, Γ, δ, q0, F) con Q = { q0 , qf }; F = {qf };

Γ = { A }; Σ = { a, b } y δ definido como sigue:
δ (q0, a, ⊥ ) = { (q0, A) , (qf, ε) } δ (qf, a, A) = { (qf, ε) }
δ (q0, a, A) = { (q0, AA) , (qf, A) } δ (qf, b, A) = { (qf, ε) }
δ (q0, b, ⊥) = { (q0, A) } δ (q0, b, A) = { (q0, AA) }
a) Da todos los cómputos posibles de M para la palabra aba
b) Demuestra que aba, aa, abb no pertenecen a L(M) y que baa, bab, baaaa
pertenecen.
c) Describe L(M) en castellano.

pág. 3
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

14. Construye un autómata con pila para cada uno de los siguientes lenguajes:

a) { anbn: n ≥ 0 }
b) { anb2n: n ≥ 0 } c) { a2nbn: n ≥ 0 }
d) { ambn: m ≤ n ≤ 2*m } e) { anbm: m ≤ n ≤ 2*m }

15. Construye un autómata con pila para cada uno de los siguientes lenguajes:

a) { w ∈ {a , b , c}* : w es capicúa }
b) { a2*i+1bi : i ≥ 0 }
c) { palabras sobre el alfabeto {( , )} con paréntesis balanceados }
Por ejemplo, "(())()(())" es una palabra válida, "()())(" y "())(()" no son
palabras válidas.
d) { expresiones regulares válidas sobre el alfabeto { a, b } }
e) El lenguaje generado por la gramática G = (N, Σ, S, P) donde N = { S };
Σ = { ( , ) , [ , ] } y P = { S → ε | SS | [S] | (S) }
f) { w ∈ { a, b }* : |w|a = 2*|w|b }
g) { aibjck : i, j, k ≥ 0, i = j ∨ j = k }
h) { aibjck : i, j, k ≥ 0, i+k = j }
i) { ai+jbicj : i, j ≥ 0 }
j) { ambn : m ≠ n }

16. Sean L1 = { a2*ib3*i : i≥0 } y L2 ={ w ∈ {a, b}* : w tiene al menos un prefijo con
más b´s que a´s}

a) Construye autómatas con pila que acepten ambos lenguajes

b) Da los cómputos asociados a las cadenas aabbb y ababbaa en cada uno de
los autómatas construidos.

17. (Ejercicio especial) Construye un autómata con pila que reconozca el lenguaje
generado por la gramática cuyas producciones son :
S → aAA A → aS | bS |a
Da una derivación y un cómputo para alguna palabra generada por la
gramática.

pág. 4
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

18. Sea el lenguaje L = {w ∈ Σ* : 2 |w|ab = |w|a} definido sobre el alfabeto Σ = {a‚ b}.
a) L es independiente del contexto. Explica cómo construir un autómata con
pila que lo reconozca.
b) Construye el autómata con pila M que reconoce este lenguaje siguiendo
las ideas del apartado anterior.
c) Escoge dos transiciones de M, de distinto tipo, e indica cuáles serían las
reglas de producción que se obtendrían al aplicar el algoritmo que
construye una gramática equivalente.

19. (Ejercicio especial) Considera el alfabeto Σ={ ( , ) } y la siguiente definición

inductiva del lenguaje L⊆Σ*
Paso básico: ()∈L
Paso de inducción: ∀k∈N x1,...,xk ∈L ⇒ (x1...xk) ∈L

a) Demuestra que no es un lenguaje regular

b) Demuestra que L es un lenguaje independiente del contexto por el método

que prefieras.

Sobre simplificación de gramáticas y FNG

20. Simplifica las gramáticas cuyas producciones vienen dadas a continuación:

a) S → AA | Bb b) S → A | aBa | AbA
C → a A → Aa | ε
B → b B → Bb | BC
A → aBaD |SBBb C → CB | CA | bB

c) S → A|B d) S → A | AA | AAA
A → C|D A → ABa | ACa | a
B → D|E B → ABa | Ab | ε
C → S|a|ε C → Cab | CC
D → S|b D → CD | Cd | CEa
E → S|c|ε E → b

pág. 5
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

e) S → ABaC f) S → Aa | Ba | B
A → AB A → Aa | ε
B → b|ε B → aA | BB | ε
C → D|ε
D → d

21. (Ejercicio especial) Sea G = (N, Σ, S, P) la gramática cuyas reglas de

producción son:

S → aSa | bSb | C | aDAb | bADa

A → aA | bA
B → aB | bB | AB | BAB | ε
C → aBb | bBBa | CA | ACA
D → aD | bDb | ε

a) Simplifica la gramática.
b) Describe razonadamente el lenguaje generado por la misma.

22. Considera la gramática independiente de contexto cuyas reglas vienen dadas a

continuación:

S → b | bHF | bH | bF G → dG | d

H → bHc | bc F → dFe | de | G

a) Construye una gramática equivalente disminuyendo el número de reglas.

Para ello introduce producciones nulas.
b) Razona cuál es el lenguaje generado por la gramática.
c) Teniendo en cuenta la estructura del lenguaje generado por la gramática,
construye otra gramática equivalente a la del apartado a) con solo seis reglas
de producción.

pág. 6
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

23. Da gramáticas en FNG equivalentes a las gramáticas cuyas producciones

corresponden a los siguientes apartados
a) S → aBAAb | bABBa | aCa b) S → AB
A → aBa | B | a |ε A → BB | CC
B → bAb | A | b | ε B → AD | CA
C → aCa | bDb C → a
D → aCa | bDb D → b

c) S → A|B d) S → Ba | Ab
A → aB | bS | b A → Sa | AAb | a
B → AB | Ba | CC B → Sb | BBa | b
C → AS | b | ε

24. Sea una gramática G = (N, Σ, S, P) cuyas reglas de producción son de la forma
∗
A → wB o de la forma A → w con A, B ∈ N y w ∈ Σ . A pesar de no ser una
gramática lineal a la derecha podemos asegurar que el lenguaje que genera la
gramática es regular. Razona por qué.

Sobre gramáticas y/o autómatas

25. Di si son ciertas o falsas las siguientes afirmaciones, razonando tu respuesta de

forma breve pero convincente.
a) La derivación de una palabra por una gramática en FNG tiene tantos
pasos como su aceptación por un AP.

b) Dado un autómata con pila existe una única gramática equivalente.

c) El símbolo inicial de cualquier gramática siempre es un símbolo útil.

d) Si M es un autómata con pila que no modifica la pila en ningún momento,

y además su estado inicial no es final, entonces necesariamente L(M) = Ø.

e) Sea G = (N, Σ, S, P) una gramática independiente de contexto y α ⇒ β una

derivación inmediata en G, tal que |α| = |β|. Entonces necesariamente α
= δAγ y β = δsγ con δ, γ ∈ (N ∪ Σ)*, A∈ N, s∈ Σ.

f) Todo lenguaje regular es independiente de contexto y ningún lenguaje

independiente de contexto es regular.

pág. 7
EJERCICIOS de MAC 1 – ALF (Tema 3) Curso 2010/2011

g) Sea G=(N, Σ, S, P) una gramática independiente del contexto en Forma

+
Normal de Greibach. Sea S ⇒ δ ⇒ γ una derivación en G. El número de
símbolos terminales en γ puede ser menor que el número de terminales en
δ.

h) Si G es una gramática tal que ε∉L(G), G no puede tener producciones

nulas.

i) Las gramáticas regulares no tienen Forma Normal de Greibach.

26. Sea el lenguaje L = { x•y: x,y ∈ {a,b}* ∧ |x| = |y|∧ x ≠ yR }. Demuestra que es
independiente del contexto. Explica detallada y razonadamente el modelo
elegido para probarlo antes de construirlo.

27. Sea el lenguaje formado por aquellas palabras sobre el alfabeto {a, b} que tienen
longitud par y tales que, o bien coinciden los dos símbolos centrales o bien
coinciden los dos de los extremos.

a) Construye una gramática independiente de contexto que lo genere.

b) Construye un autómata con pila que lo reconozca. Puedes construirlo
directamente (con las explicaciones oportunas) u obtenerlo del apartado
anterior mediante algún algoritmo de transformación.

28. Sea el lenguaje L = { anbn: n no es múltiplo de 5 }.

a) Demuestra que es independiente de contexto construyendo un autómata

que lo reconozca, y explicando detalladamente su funcionamiento.
b) Sea ahora L = { anbn: n es múltiplo de 5 .}.¿Cómo modificarías el autómata
construido en el apartado anterior para que acepte este lenguaje?

n m
29. Sea L = {a b : n = m ó n = 3m }.
a) Demuestra que L es un lenguaje independiente del contexto construyendo
una gramática que lo genere.
b) Demuestra que L es un lenguaje independiente del contexto construyendo
un autómata con pila que lo reconozca. Puedes construirlo directamente
(con las explicaciones oportunas) u obtenerlo del apartado anterior
mediante algún algoritmo de transformación.

pág. 8