MODELOS DE COMPUTACIÓN

RELACION DE PROBLEMAS 4.

1. Determinar si la siguiente gramática es ambigua y si el lenguaje generado es inherente-

mente ambiguo:

S → A1 , A2

A1 → aA1 b, aA1 , 

A2 → aA2 b, A2 b, 

2. Sea la gramática
S → aSA, S → , A → bA, z A → 

a ) Demostrar que es ambigua

b ) Dar una expresión regular para el lenguaje generado.

c ) Construir una gramática no ambigua que genere el mismo lenguaje

3. Describe el lenguaje generado por la siguiente gramática G = ({S, A}, {a, b}, P, S), con

P = {S → aAa, S → bAa, A → aAa, A → bAa, A → }

Demuestra que el lenguaje generado por la gramática no es regular, pero si indepen-

diente del contexto,
Normaliza la gramática G en la Forma Normal de Greibach, y determina todas la
derivaciones más a la izquierda para la cadena ab2 a5 .

4. Obtener la forma normal de Greibach para la siguiente gramática:

< {S1 , S2 , S3 }, {a, b, c, d, e}, S1 , P >

donde
P = {S1 → S1 S2 c, S3 , S3 bS3 ; S2 → S1 S1 , d; S3 → S2 e}

5. Considera la gramática G = (V, T, S, P ) donde

V = {< expresion >, < identif icador >}, T = {a, b, c, d, −}, S =< expresion >

y P contiene las producciones:

< expresion >→< identif icador >

< expresion >→< identif icador > − < expresion >

< expresion >→< expresion > − < identif icador >

< identif icador >→ a, b, c, d

1
 demuestra que esta gramática no puede ser empleada para describir un posible len-
guaje de programación, teniendo en cuenta que que la sustración no es una operación
conmutativa, y que (a − b) − d 6= a − (b − d),
¾es ambígua la gramática G? ¾es la ambiguedad inherente al lenguaje generado por
G ? Justica adecuadamente la respuesta.

¾es posible modicar G de manera que la nueva gramática pueda ser usada para
generar el lenguaje de las expresiones aritméticas correctas con el operador de resta

6. Dada la gramática
S → A, S → B, A → aaA, A→

B → aaaB, B→

Demostrar que es ambigua

Construir un autómata nito determinístico que acepte el mismo lenguaje
Construir una gramática lineal por la derecha, a partir del autómata determinístico,
que genere el mismo lenguaje,
Demostrar que la gramática resultante no es ambigua.

7. Dar una gramática libre de contexto no ambigua que genere el lenguaje L = {ai bj ak bl : (i = j) ∨ (k = l)}.

8. Determinar cuales de las siguientes gramáticas son ambiguas y, en su caso, comprobar si

los lenguajes generados son inherentemente ambiguos:

a ) S → aSb|Sb|aS|a

b ) S → aaS|aaaS|a

c ) S → aS|aSb|X
X → Xa|a

9. Dar gramáticas libres de contexto o regulares (cuando sea posible) para los siguientes
lenguajes sobre el alfabeto A = {a, b, c}:

a ) L1 = {ai bj ck : i 6= j ∨ j 6= k}

b ) L2 = {(ab)i (bc)j : i, j ≥ 0}

c ) L3 = {ai bi+j cj : i, j ≥ 0}

d ) L4 denido como el conjunto de palabras que comienzan por aab y terminan por bbc
y tales que estas dos subcadenas no aparecen nunca en el interior de la palabra (sólo
están al principio y al nal).

2
10. Pasar a forma normal de Greibach la gramática

S → AAA, S→B
A → aA, A→B
B→

11. Dada la gramática:

S → 01S, S → 010S, S → 101S, S → ,

determinar si es ambigua.
Construir un autómata nito determinista asociado y calcular la gramática lineal por la
derecha que se obiene a partir del autómata. ¾Es ambigua la gramática resultante?

12. Demostrar que la gramática: S → A1B, A → 0A|, B → 0B|1B| no es ambigua.

Encontrar una gramática para el mismo lenguaje que sea ambigua y demostrar su ambi-
güedad.

13. Determina si los siguientes lenguajes son regulares o independientes del contexto. Encuen-
tra una gramática que los genere.

a ) L1 = {ai bj ck | i, j ≥ 0, k < i + j}.

b ) L2 = {(ab)i cj d | j = i − 1, i ≥ 1}.

c ) L3 = {abi cdj | j = 2 ∗ i, 1 ≤ i ≤ 10}.

Elige una de ellas que sea independiente del contexto y pásala a forma normal de Chomsky.

14. Dar gramáticas independientes del contexto que generen los siguientes lenguajes sobre el
alfabeto A = {0, 1}:

a ) L1 : conjunto de palabras tal que si la palabra empieza por 0, entonces tiene el mismo
número de 0s que de 1s.
b ) L2 : conjunto de palabras tal que si la palabra termina por 1, entonces tiene un
número de 1s mayor o igual que el número de 0s.
c ) L1 ∩ L2 .

15. Dadas las siguientes gramáticas determinar si son ambiguas y, en caso de que lo sean,
determinar una gramática no ambigua que genere el mismo lenguaje

3
 a ) E → E + E|E ∗ E|(E)|x|y (alfabeto de símbolos terminales {x, y, +, ∗, (, )} y símbolo
inicial E ).
b ) S → SS + |SS ∗ |x|y (alfabeto de símbolos terminales {x, y, +, ∗} y símbolo inicial
S)

16. Una gramática independiente del contexto generalizada es una gramática en el que las
producciones son de la forma A → r donde r es una expresión regular de variables y
símbolos terminales. Una gramática independiente del contexto generalizada representa
una forma compacta de representar una gramática con todas las producciones A → α,
donde α es una palabra del lenguaje asociado a la expresión regular r y A → r es una
producción de la gramática generalizada. Observemos que esta gramática asociada puede
tener innitas producciones, ya que una expresión regular puede representar un lenguaje
con innitas palabras. El concepto de lenguaje generado por una gramática generalizada
se dene de forma análaga al de las gramáticas independientes del contexto, pero teniendo
en cuenta que ahora puede haber innitas producciones. Demostrar que un lenguaje es
independiente del contexto si y solo si se puede generar por una gramática generalizada.

17. Demostrar que los siguientes lenguajes son independientes del contexto:

a ) L1 = {u#w | u−1 es una subcadena de w, u, w ∈ {0, 1}∗ }

b ) L2 = {u1 #u2 # . . . #uk | k ≥ 1, cada ui ∈ {0, 1}∗ , y para algún i y j, ui = u−1

j }

18. Sobre el alfabeto {0, 1} dar una gramática que genere todas las palabras en las que el
número de 0s es el doble que el de 1s.

19. Sea el lenguaje L = {u#v k u, v ∈ {0, 1}∗ , u 6= v}, demostrar que es independiente del
contexto.

20. Demostrar que si una gramática G está en forma normal de Chomsky, entonces si w ∈
L(G) el número de pasos de derivación de toda generación de esta palabra es 2|w| − 1.

21. Dar gramáticas independientes del contexto no ambiguas para los siguientes lenguajes
sobre el alfabeto {0, 1}:

a ) El conjunto de palabras w tal que en todo prejo de w el número de 0s es mayor o

igual que el número de 1s.
b ) El conjunto de palabras w en las que el número de 0s es mayor o igual que el número
de 1s.

22. Sea L = {0i 1j k i 6= j, 2i 6= j}. Demostrar que L es independiente del contexto.

4
23. Supongamos el conjunto de símbolos terminales T = {if, condicion, then, else, a := 1}, el
alfabeto de variables V = {< SEN T >, < IF − T HEN >, < IF − T HEN − ELSE >
, < ASIG >}, y las producciones:

< SEN T >→< ASIG > | < IF − T HEN > | < IF − T HEN − ELSE >
< IF − T HEN >→ if condition then < SEN T >
< IF − T HEN − ELSE >→ if condition then < SEN T > else < SEN T >
< ASIG >→ a := 1

Suponiendo que el símbolo inicial es < SEN T >, demostrar que la gramática es ambigua.
Dar una gramática no ambigua que genere el mismo lenguaje.