CENTRO DE INVESTIGACIÓN EN COMPUTACIÓN

TEORIA DE LA COMPUTACIÓN

SEMESTRE A19

Abdiel Reyes Vera

Problema 1

Encontrar el lenguaje generado por la gramática G={V,∑,R,S} dada por:

V = {S,M,N}
∑ = {x,y,z}
R = { S → MzN
M → xM | ε
N → yN | ε }
¿De qué tipo son la gramática y el lenguaje generado por ella?

𝐿(𝐺) = {𝑥𝑖𝑧𝑦𝑗 |𝑖, 𝑗 ≥ 0}

La gramática es una GLC pero no es regular, y el lenguaje es un LLC pero tampoco es regular.

Problema 2

Hallar una GLC que genere 𝐿 = {𝜔𝜔𝑅 |𝜔 𝜖 {0,1}∗ }

G = {V, ∑, R, S} dada por:
V = {S0, S, A, B}
∑ = {0,1} S = S
R = { S → A| B
A → 0S0 | ε
B → 1S1 | ε }
Problema 3

Calcular una GLC que reconozca: L= { ambn /n ≤ m ≤ 2n}

G= ({A,B}, {a,b}, R, A ). Con R= {A → aB
B → b| aAb | ab }

Problema 4

Construir una gramática que genere el siguiente lenguaje: 𝐿 = {𝑎𝑖𝑏 𝑗𝑐𝑖+2𝑗 |𝑖, 𝑗 ≥ 0}
Problema 5

Hallar la gramática que genera el lenguaje reconocido por el siguiente autómata:

Q={A,B,C,D,E}
∑={0,1} S=S
R={ S → A
A → 0B | 1A B → 0B | 1C C → 0B | 1D
D → 0E | 1A | ε
E → 0D | 1C | ε }
Problema 6

Construir el autómata que reconoce el lenguaje generado por la siguiente gramática: G = {V, T,

P, S} dada por:
V = {S, A, B}
T = {0,1}
P = { S → 1B | 1
A → 1B | 1
B → 0A
}

Problema 7

Limpiar la siguiente gramática y decir de qué tipo es G = {V,

T, P, S} dada por:
V = {S, A, B, C, D, E, F}
T = {a, b, c, d}
P = { S → CcE | C | SC | S | BE A
→ AC | b | AEC | CA
B → ab | CA | CC | CF
C → CE | ε | aA | CC D
→ ADC | ED | CEB
E → aED | EC | D F
→d | SC | AC }
 Gramática Limpia: Y es de tipo 2 (gramática
libre de contexto)
G = {V, T, P, S} dada por:
V = {S, A, C, F}
T = {a, b, d} P={
S → C | SC
A → AC | b | CA
C → ε | aA | CC F
→d | SC | AC }
Problema 8

Limpiar la siguiente gramática y poner la gramática resultante en forma normal de Chomsky G = {V, T,
P, S} dada por:
V = {S, A, B, C, D, E, F}
T = {a, b, c, d}
P = { S → AcB | A | SA | S | EB
A → AB | ε | aC | AA
B → aBD | BA | D FNC:
C → CA | b| CBA | AC S0 → aC | AA | SA |
D → CDA | BD | ABE ε S → aC | AA | SA
E → ab | AC | AA | AF F A → aC | AA
F→ d | SA | CA } C → CA | b | AC
G = {V, T, P, S} dada por: F →d | SA | CA | b | AC | aC | AA |
V = {S, A, C, F} SA }
T = {a, b, d}
P{ S → A | SA
A → ε | aC | AA
C → CA | b | AC
F →d | SA | CA }

Problema 9

Sea G = {V, T, P, S} donde: V

= {S, S1, I}
T = {a, b}
P = { S → aSa | S1
S1 → bI
I → aIa | b }

a) Calcular L(G)
b) ¿Es L(G) regular? En caso afirmativo encontrar G’ regular tal que L(G) = L(G’), y en caso
negativo demostrarlo utilizando el Lema de Pumping.
c) Calcular la FNC
 𝐿 = {𝑎𝑖 𝑏𝑎𝑗 𝑏𝑎 𝑗 𝑎𝑖 |𝑖, 𝑗 ≥ 0}
FNC:

S → JK | LI S1 → LI
I → JM | b J →
a
K → SJ
L → b M → Ia
Problema 10

Sea G = {V, ∑, R, S} la siguiente gramática:

V = {S, A, B, C, D, E}
∑ = {a, b}
R={ S→A|B
A → aCb | ε
B → aD | ε
C → aA | aAb
D → bB | aE
E → bD }

a) Determínese L(G)
b) ¿Es L(G) regular? ¿por qué?
𝐿 = {(𝑎𝑖 𝑎𝑗 𝑏𝑖 )𝑈(𝑎𝑖 𝑏𝑗 )𝑘 | 𝑖, 𝑗, 𝑘 ≥ 0}

Un lenguaje es regular si existe un AF o una expresión regular que lo reconozca. Al tener producciones del tipo
A → aCb en el lenguaje final vamos a tener el mismo número de a´s con el mismo número de b´s, cosa que los
AF no pueden generar. Esto sí se puede representar con un AP pero eso solo indica que es un Lenguaje Libre
de Contexto. Por lo anterior el lenguaje no es regular.

Problema 11

Sea G = {V, T, P, S} :
V = {S, X, Y, A}
T = {a, b, 0, 1} P
={ S → XY
X → 0X1 | ε
Y → aY | A
A → bA | ε }

a) Determínese L(G)
b) ¿Es L(G) regular? Razónese convenientemente la respuesta.
c) Calcúlese la FNC

𝐿 = {0𝑖 1𝑖 𝑎𝑗 𝑏𝑘 |𝑖, 𝑗, 𝑘 ≥ 0}

Igual que en el ejercicio anterior se tiene una producción del tipo X → 0X1 por lo que se tiene que generar el
mismo número de 0´s con el mismo número de 1´s, por lo tanto el lenguaje no es regular ya que no hay un AF
que lo describa.
FNC:

S0 → XY | CF | CD | EY | a | BA | b | ε S → XY |
CF | CD | EY | a | BA | b
X → CF | CD
Y → EY | a | BA | b A → BA |b
B→b
C→0
D→1
E→a
F → XD
Problema 12

Dado el lenguaje 𝐿 = {𝑎 𝑛 𝑎𝑐 𝑚 𝑎𝑏𝑛 | 𝑛, 𝑚 ≥ 0} hallar:

a) Una gramática G(L) que genere L.

b) Poner G(L) en Forma Normal de Chomsky
c) Poner G(L) en Forma Normal de Greibach

G = ({S, A, B}, {a, b, c}, P, S) donde:

P={S→A
A → aAb | aBa
B → cB | ε }
FNC FNG
S → FD | GC | CC S → aAD | aBC | aC
A → FD | GC | CC A → aA D | aBC | aC
B → EB | c B → eB | c
C→a C→a
D→b D→b
E→c E→c
F → CA F → aA
G → CB G → aB

Problema 13

Sea G = ({S, A, B, C, D}, {a, b, c}, P, S) donde: P

={ S → AC
A → aBb
B → aAb | ε
C → CD | ε
D → cD | c }
a) ¿L(G)?
b) Demuéstrese formalmente si L(G) es o no regular.
c) Forma Normal de Chomsky
d) Determínese, utilizando el algoritmo CYK, si abcc pertenece a L(G). Analícese el
significado del contenido de las casillas (2,2) y (1,3).
𝐿 = {𝑎 𝑛 𝑏𝑛 𝑐 𝑚 | 𝑛 ≥ 1 𝑒 𝑖𝑚𝑝𝑎𝑟 , 𝑚 ≥ 0}
L(G) es regular si existe un AF que lo reconozca, al tener la gramática producciones del tipo A → aBc, se
necesitaría guardar en memoria el número de a’s al principio para dar el mismo número de c’s al final,
consideración que no se puede hacer con un AF, por lo tanto L(G) no es regular.
S → AC | HF | EF
A → HF | EF
B → IF
C → CD | GD | c
D → GD | c
E→a
F→b
G→c
H → EB
I → EA
 abcc
S
abc bcc
S S
ab bc cc
B,S,A,I,H - D,C
a b c c
I,E,A,S,H F,S,A,B G,D,C G,D,C
a b c c

En la celda 2,2 no tenemos ninguna producción que genere la derivación bc y por eso se marca como vacía.

En la celda 1,3 tenemos que con la producción S podemos llegar a la derivación abcc y por ello decimos que si
en esta celda llegamos al axioma, entonces es posible llegar a esa derivación con la gramática y por lo tanto la
derivación pertenece a L(G).
Problema 14

a) Encuéntrese la Forma Normal de Greibach (respetando el orden de las variables) de la gramática

({A1, A2, A3}, {a, b}, P, A2) donde:
P={ A1 → A2b | ε
A2 → A1A3 | A3a | A1a
A3 → ab | aA1 }

b) Sea X = {a, b, c}. Determínese una Gramática Libre de Contexto que genere el lenguaje sobre X
𝐿 = {𝑎𝑖𝑏 𝑗 𝑐 𝑘 | 𝑖, 𝑘 ≥ 0, 𝑗 ≥ 1, 𝑘 = 2𝑗 ó 𝑘 = 2𝑖 }
a)
1. A1 → aA5 A4A5 A3 A5 | aA1A4 A5 A3A5 | aA4A5 A3A5 | aA5 A5 A3A 5 | aA1A5 A3 A5| aA5A3 A5 | aA5A4 A5A4A5 |
aA1A4A5A4 A5 | aA4 A5A4A5 | aA5A5A4 A5 | aA1A5A4A5 | aA5A4 A5 | aA5A4 A5
2. A2 → aA5 A4A5 A3 A5 A3 | aA1A4A5 A3 A5 A3 | aA4A5 A3A5A3 | aA5A5A3 A5 A3 | aA1A5 A3 A5A3 | aA5A3 A5A3|
aA5A4A5 A4 A5 A3 | aA1A4 A5A4 A5 A3 | aA4 A5A4 A5A3| aA5A5 A4 A5A3| aA1 A5 A4 A5A3 | aA5A4 A5A3 | aA5 A4A5 A3
|aA5A4 A5 A3A5 A4| aA1 A4 A5A3 A5 A4 | aA4A5A3 A5 A4| aA5A5 A3 A5A4 | aA1A5A3 A5 A4| aA5 A3A5 A4 | aA5A4 A5 A4 A5A4 |
aA1A4A5 A4 A5A4 | aA4A5 A4A5 A4 | aA5 A5A4 A5 A4 | aA1A5A4 A5 A4| aA5A4 A5A4 | aA5A4 A5A4 | a A5A4 | aA1A4 | aA4 |
aA5 | aA1 | a
1. A3 → aA5 | aA1 | a
2. A4 → a
3. A5 → b
4. A1→ aA5A4 A5 | aA1A4 A5 | aA4A5 | aA5 A5 | aA1A5| aA5
b)
G = {V, ∑, R, S} dada por:
V = {S, A, B, C, D}
∑ = {a, b} S = S

R = { S → b | bcc | bAcc | Bbcc | BbAcc | D A → bcc | bAcc

B → a | aB
C → aCcc | D
D → b | bD }
Problema 15

a) Dado el lenguaje formal L sobre el alfabeto {a ,b} definido como sigue:

𝐿 = {𝑐𝑎𝑑𝑒𝑛𝑎𝑠 𝑑𝑒 𝑎 ′ 𝑠𝑦 𝑏 ′ 𝑠 𝑒𝑛 𝑒𝑠𝑒 𝑜𝑟𝑑𝑒𝑛 𝑡𝑎𝑙𝑒𝑠 𝑞𝑢𝑒 𝑝𝑎𝑟𝑎 𝑐𝑎𝑑𝑎 𝑎 𝑑𝑒 𝑙𝑎 𝑐𝑎𝑑𝑒𝑛𝑎 ℎ𝑎𝑦𝑎 𝑢𝑛𝑎 𝑜 𝑑𝑜𝑠 𝑏′𝑠}

Encuéntrese la GLC, G, tal que L(G) = L

Realícese un árbol de derivación y una derivación más a la derecha en G para la cadena aabbb.
¿Es L regular? Demuéstrese,

b) Sea G = ({S, X, Y, Z, A, B}, {a, b}, P, S) una GLC donde P

= { S → X |Y
X → aZb | bZa
Z → aZb | bZa | ε
Y → aB | bA
B → b | bB
A→a

Contestar razonadamente las siguientes cuestiones:

i) Dar una expresión formal del lenguaje L: L=L(G)
ii) Determinar las formas normales de Chomsky y Greibach
iii) Determínese por el algoritmo CYK la pertenencia o no a L(G) de la cadena aabb
iv) A partir de la tabla del algoritmo CYK anterior razonar la respuesta a las siguientes cuestiones: ¿qué
subcadenas de esta palabra también pertenecen a L(G)? ¿qué subcadenas pertenecerían al lenguaje si
el símbolo inicial fuera B? ¿qué significa que el contenido de una casilla sea (-)

Inciso a)

G = {V, ∑, R, S} dada por:

V = {S, A, B, C}
∑ = {a, b}
S=S
R={S→A
A → aAb | aAbb | ε }
Derivación más a la derecha:

S→A
→ aAb
→ aaAbbb
→ aabbb

Inciso b)

i) 𝐿 = { (𝜔1𝜔2) ∪ (𝑎𝑏𝑖) ∪ (𝑏𝑎) | 𝜔1, 𝜔2 ∈ 𝑋∗, 𝑖 ≥ 1 }

ii) Determinar las formas normales de Chomsky y Greibach

FNC FNG

S → DC | EA | AB | BA S → aZC | bZA | aB | bA
X → DC | EA X → aZC | bZA
Z → DC | EA | AC | CA Z → aZC | bZA | aC | bA
Y → AB | BA Y → aB | bA
B → b | CB B → b | bB
A→a A→a
C→b C→b
D → AZ
E → CZ
 iii) Determínese por el algoritmo CYK la pertenencia o no a L(G) de la cadena aabb

S, X, Z, D
S, X, Z, D Y, S, X, Z
D S, X, Z, D, Y E, B
A, S, X, Z, Y, D A, S, X, Z, Y, D C, S, X, Z, Y, B, E C, S, X, Z, Y, B, E
a a b b

La cadena SI pertenece a L(G) porque tenemos en la última casilla a S, es decir, podemos llegar a ella partiendo
del axioma.

iv) A partir de la tabla del algoritmo CYK anterior razonar la respuesta a las siguientes cuestiones:
¿qué subcadenas de esta palabra también pertenecen a L(G)? ¿Qué subcadenas pertenecerían al lenguaje
si el símbolo inicial fuera B? ¿Qué significa que el contenido de una casilla sea (-)

Las subcadenas que también pertenecen a L(G) según el CYK de arriba son abb y b

aabb
aa abb
- ab -
a a b b

En cambio, si el símbolo incial fuera B entonces sí aceptaría palabras que empiecen con dos ‘b’s. El que una
casilla tenga (-) significa que esa subcadena no tiene producciones que la produzcan.

Problema 16

Considérese la siguiente GLC G=(V,T,P,S) donde V={S,

A, B, C, D}, T={a, b, d}
P= { S → aD | bB | aBA | CA
A → AA | EA
B → Ab | bS | ε
C → ad | CA | S | BB D
→ Ea | Bd |aS
E → A | AAb | Ea }

Calcular las formas normales de Chomsky y Greibach. Determínese asimismo L(G) y la pertenencia al
mismo de la palabra w= bbaab utilizando el algoritmo CYK. A la vista de la tabla utilizada en el
algoritmo anterior ¿qué prefijos de w pertenecen a L(G’) siendo G’ = (V, T, P, B)?

FNC

S → FD | GB | FI | CA | b | FA A → AA | EA
B → AG | GS
C → FH | CA | FD | GB | FI | CA | b | FA | BB | AG | GS
D → EF | BH | FS | d
E → AA | EA | AJ | EF
F→a
G→b
H→d
I → BA
J → AG
FNG

S → aD | bB | b B → bS
D → bSH | aS | d F → a
G →b H → d

Determinar L(G)
𝐿(𝐺) = {𝑎𝑖𝑏𝑗𝑑 𝑘 | 𝑖,𝑘 ≥ 0,𝑗 ≥ 1 }

Determinar la pertenencia de la palabra bbaab a L(G)

S, C, B
S, C S, B
S, B, C B,C S, C
S, C, B B, C D, S, E, C D
G, S, B, C, J G, S, B, C, J S, F, C, D, E S, F, C, D, E G, S, B, C, J
b b a a b

bbaab
baab
bba baa
bb ba
b b b
b b a a b

Problema 17

a) Sea
𝐿 = {𝑎𝑖 𝑏𝑐𝑗 𝑎𝑘 | 𝑖 = 𝑗 + 𝑘 ó 𝑘 = 𝑖 + 𝑗; 𝑖, 𝑗, 𝑘 ≥ 0 }
• Encontrar una gramática libre de contexto G tal que L = L(G)
• ¿Es G regular? En caso negativo indicar una producción de G que demuestre su no
regularidad
• ¿Es L(G) regular? Demuéstrese.

b) Pasar a FNG la siguiente GLC G=({A1, A2, A3, A4}, {a, b}, P, A2) donde: P =
{ A1 → A2a
A2 → A1A3 | A4a
A3 → ba | A1 A1 A4 A4
→ A2b | bA4
}
GLC tal que L = L(G)

G=(V, ∑, R, S) donde V={S, A, B, C,

D, E, F, G},
∑={a, b, c}
R= { S→b|A|B|C|D|E
A → b | aAa
B → b | aBc
C → aBa| aCa
D → b | bcGa
 E → ca | cEa
F → aFc | b
G → aGa | D }

G no es regular porque contiene producciones como F → aFc, A → aAa, B → aBc, etc. Aplicamos
el lema del bombeo para demostrar que L(G) es regular.
Si L es un LC regular, entonces existe un número N > 0 talque toda cadena w ϵ L de largo y |w| >N se puede
escribir como w= xuyvz de modo que uv ≠ ε, |uyv| ≤ N y ∀𝑛 ≥ 0, 𝑥𝑢𝑛 𝑦𝑣𝑛 𝑧 𝜖 𝐿

𝐿 = {𝑎𝑖 𝑏𝑐𝑗 𝑎𝑘 | 𝑖 = 𝑗 + 𝑘 ó 𝑘 = 𝑖 + 𝑗; 𝑖, 𝑗, 𝑘 ≥ 0 }
Si j=1, k=1, i=1+1=2.
𝐿 = {𝑎𝑎𝑏𝑐𝑎 }
N=3
Si asignamos a cada letra respectivamente con xuyvz, tendríamos entonces la siguiente forma
𝐿={𝑎𝑎 3𝑏𝑐3𝑎 }con lo que ai sigue cumpliendo con la función i=j+k 𝐿={𝑎𝑎𝑎𝑎𝑏𝑐𝑐𝑐𝑎}={𝑎4𝑏𝑐3𝑎1}
donde i= 3+1=4
Por lo tanto L(G) SI es regular.

Problema 18

a) Construir una Gramática Libre de Contexto generadora del siguiente lenguaje:

𝐿 = {𝑎𝑛𝜔1𝑏𝑟+𝑠𝜔2𝑏𝑛 | 𝜔1, 𝜔2 𝜖 𝑋∗, |𝜔1| = 𝑟, |𝜔2| = 𝑠, 𝑛 ≥ 0 𝑦 𝑟, 𝑠 ≥ 1}

Pasar la gramática anterior a F.N. Greibach y demostrar si L es o no un lenguaje regular.

b) Dada la GLC G= ({S, A, B, C, D}, {a, b}, P, S) donde: P

={ S → aAa | Caa | bAb | DaC
A → aSa | CC | bSb B
→ ab | DC | aBb C →
BbD | ε
D → CaD | BDb }

Determinar L(G) y la pertenencia al mismo de abaaba mediante el algoritmo CYK.

Inciso a)

G = {V, ∑, R, S} dada por:

V = {S, A, B, C}
∑ = {a, b} S = S
R={ S→A
A → aAb | BC
B → aBb | bBb | ab | bb
C → bCa | bCb | ba | bb }

FNG

S → aAE | aBEC | bBEC | aEC | bEC A → aAE |

aBEC | bBEC | aEC | bEC B → aBE | bBE | aE | bE
C → bCD | bCE | bD | bE D → a
E→b

Un lenguaje es regular si existe un AF o una expresión regular que lo reconozca. Al tener producciones del tipo A → aAb
en el lenguaje final vamos a tener el mismo número de a´s con el mismo número de b´s, cosa que los AF no pueden
generar. Esto sí se puede representar con un AP pero eso solo indica que es un Lenguaje Libre de Contexto. Por lo anterior
el lenguaje no es regular.

Inciso b)
𝐿 = {𝜔1𝜔2𝜔1𝑅 | 𝜔1, 𝜔2 𝜖 {𝑎, 𝑏}∗}
 S, B, A, G
A, I, D A, L
S, A, C, G, H - J, A, C
S, A, C, H M B S, A, C
B, I, A, D, N M, G, K, L S, A, B, D B, L, C, N, D K, G, M
E, S, A, B, D, S, A, B, F, I, E, S, A, B, D, E, S, A, B, D, S, A, B, F, I, E, S, A, B, D,
G, H, K M, N, O G, H, K G, H, K M, N, O G, H, K
a b a a b a

Como tenemos al axioma (S) en la última casilla, entonces abaaba sí pertenece a L(G)
Problema 19

Sea 𝐿 = {𝑎𝑛+2𝑠𝑏2(𝑠+𝑡)+1𝑐2𝑡+𝑛+1 | 𝑛 > 0, 𝑠, 𝑡 ≥ 0 }

a) Constrúyase una GLC que genere L.

b) ¿Es L regular?
c) Construir un árbol de derivación cuya producción sea aaabbbc

}
Problema 20

Sea G1= ({X1, X2, X3, X4, X5, X6}, {a,b}, P, X1) donde

P={ X1 → X1X5a | X2a | X5X6

X2 → X1a | X4
X3 → aaX3 | ε
X4 → X3b | X5a
X5 → X4X5 | X1aX5
X6 → a | b}

Determínese L(G1)

Sea M2 el autómata definido por el siguiente diagrama de transiciones:

Determínese la Gramática regular tal que L(G2) = L(M2) así como L(M2)

b) Sea G la gramática tal que L(G) = L(G1) U L(G2). Determínese la FNC y la FNG de G.

𝐿 = {(𝑎𝑏𝑖𝑎 ∪ 𝑏 𝑗 𝑎)(𝜀 ∪ [𝑏 𝑘 (𝑎 𝑙 ∪ 𝑎 𝑙𝑏𝑚 𝑎)]𝑛 ) | 𝑗, 𝑙, 𝑚, 𝑛 > 0, 𝑖, 𝑘 ≥ 0}

G2 = ({S, q0, q1, q2, q3, q4, q5}, {a, b}, Q, S) donde

Q= { q0 → aq1 | bq2
q1 → bq1 | aq3
 q2 → bq2 | aq3
q3 → bq3 | aq4 | ε
q4 → aq4 | bq2 | ε
q5 → aq1 | bq2

G = ({X1, X2, X3, X4, X5, X6, q0, q1, q2, q3, q4, q5}, {a,b}, R, S) donde

FNC
S → X1 | q0
R= { S → X1 | q0 X1 → X9X7 | X2X7 | X5X6
X1 → X1X5a | X2a | X5X6 X2 → X1X7 | X3X8 | X5X7 | b
X2 → X1a | X4 X3 → X10X3 | X7X7
X3 → aaX3 | ε X4 → X3X8 | X5X7 | b
X4 → X3b | X5a X5 → X4X5 | X11X5
X5 → X4X5 | X1aX5 X6 → a | b
X6 → a | b X7 → a
q0 → aq1 | bq2 X8 → b
q1 → bq1 | aq3 X9 → X1X5
q2 → bq2 | aq3 X10 → X7X7
q3 → bq3 | aq4 | ε X11 → X1X7
q4 → aq4 | bq2 | ε q0 → X7q1 | X8q2
q5 → aq1 | bq2 } q1 → X8q1 | X7q3 | a
q2 → X8q2 | X7q3 | a
q3 → X8q3 | X7q4 | b | a
q4 → X7q4 | X8q2 | a
q5 → X7q1 | X8q2

FNG
1. S → X1 | q0
2. X2 → aX7X3X8X7X9X7 | aX7X8X7X9X7 | bX7X9X7 | aX7X3X8X7X7 | aX7X8X7X7 |
bX7X7 | aX7X3X8 | aX7X8 | b
3. X1 → aX7X3X8X7X9 | aX7X8X7X9 | bX7X9 | aX7X3X8X7 | aX7X8X7 | bX7
4. X3 → aX7X3 | aX7
5. X4 → aX7X3X8 | aX7X8 | b
6. X6 → a | b
7. q0 → aq1 | bq2
8. q1 → bq1 | aq3 | a
9. q2 → bq2 | aq3 | a
10. q3 → bq3 | aq4 | b | a
11. q4 → aq4 | bq2 | a
12. q5 → aq1 | bq2
13. X7 → a
14. X8 → b
15. X9 → aX8X9 | aX7X3X8X7 | aX7X8X7 | bX7
Problema 21

Considérese el lenguaje formal: L1 = {w1 a w2 b | w1, w2 ϵ {a,b}*, |w1| = |w2|}, y la gramática G2= ({S, A,
B, C, D}, {0,1}, S, P) cuyo conjunto de producciones es:

P={ S → 0C | B | 1D | ε
A → 1S | B
B → 0S C
→ 1A D
→ 0B }

a) Describir de alguna forma L(G2) y calcular una gramática G3 generadora del lenguaje
formado a partir de la concatenación de L1 con L(G2).
b) Discutir la regularidad de L1 y de L(G2)
c) Sea ahora w = babb0 una palabra perteneciente a G3. Dar un árbol de derivación cuya
producción sea w.

𝐿(𝐺2) = {𝜔3| 𝜔3 𝜖 {0,1}∗ }

G1= ({M, U}, {a, b}, Q, M) cuyo conjunto de producciones es:

Q={ M → UMU | ε
U→a|b }

G3= ({T, S, A, B, C, D, M, U}, {a, b, 0, 1}, R, T) cuyo conjunto de producciones es: R = { P →

UMU0C | UMUB | UMU1D | UMU | S | ε

M → UMU | ε U → a | b
S → 0C | B | 1D | ε A → 1S | B
B → 0S C → 1A
D → 0B }
Problema 22

Sea G = (V, T, S, P) una GLC donde V={S, A, B, C, D, E}; T={a, b}; P =

{ S → CASB | C
A → aAb | ε
B → bBa | CDA | ba C
→ ε | aDE
D → aD | CDa E
→ ab | ba }
Se pide:

a) Demostrar que la cadena abba pertenece a L(G) mediante un árbol de derivación y mediante
el algoritmo CYK.
b) Demostrar que la gramática de partida G resulta ser equivalente a la gramática

G’ = ({S, A, B}, {a, b}, { S→ ASB | ε

A → aAb | ε
A → bBa | ba})

c) Calcular la FNG de G
 Inciso i)

No hay una GLC que lo describa

Inciso ii) FNC

Como no hay recursividad a la izquierda no Se ponen en la FNC

hace falta agregar una variable al inicio. Se
eliminan las reglas A → ε
S → AF | HF | CD
A → FI
S → Aa | aAa | CD B → GB | b
A → aSa C → JG | FB | a
B → bB | b D → FD | GB | b | a
C → aCb | aB | a E → FB | a
D → aD | bB | b | a F→a
E → aB | a G→b
F→a H → FA
G→b I → SF
J → FC
Inciso c) FNG DE G:
1. S → ε | aAGSB | aGSB | bBF | bF | aAGB | aGB | aAGSBH | aGSBH | bBFH | bFH | aAGBH |
aGBH | aAGSB | aGSB | bBF | bF | aAGB | aGB
2. H → bBFH | bFH | bBF | bF
3. A → aAG | aG
4. B → bBF | bF
5. E → aG | bF
6. F → a
7. G → b

Problema 23

Sea la gramática libre de contexto G = ({S, A, B, C}, {a, b}, S, P) donde: P = {

S → AB | BC
A → AB | a
B → AA | CB | b
C→a|b }
Pasarla a FNG considerando como orden de las variables el siguiente S, A, B, C.
FNG
S → aDB | aB | aDAC | aAC | aBC | bBC | bC
D → aDAD | aAD | aBD | bBD | bD | aDA | aA | aB | bB | b B → aDA |
aA | aB | bB | b
A → aD | a C → a | b
Problema 24

i) Dado el lenguaje siguiente 𝐿 = {𝑎 𝑛 𝑏𝑚 𝑐 𝑝 𝑎 𝑞𝑏 𝑛 | 𝑛𝑞 = 𝑝 + 𝑚; 𝑚, 𝑛 > 0, 𝑝 ≥ 0 }

a) Determinar una GLC G tal que L(G) = L
b) Demostrar si son o no regulares tanto G como L.

ii) Dada la GLC G = ({S, A, B, C, D, E}, {a,b}, P, S) donde P

={ S → Aa | aAa | CD
A → aSa B
→ bB | ε
C → aCb | E
D → aD | bB | ε E
→ ab }

a) Determínese L(G)
b) Obtener, siguiendo los procedimientos oportunos, las formas normales de
Chomsky y Greibach.
c) Demuéstrese si es cierto que aabaa ϵ L(G) utilizando el algoritmo CYK.
 A) No hay una GLC que la describa
B)

C)
Partimos de la gramática limpia obtenida en el 1er paso al calcular la FNC, y observamos que solo falta sustituir A en S
para obtener la FNG.

1. S → aSFF | a aSFF | aCGD | aBD | aD

2. A → aSF
3. B → bB | b
4. C → aCG | aB | a
5. D → aD | bB | b | a
6. E → aB | a
7. F→a
8. G→b

S, I
S, I S
S, I, C C S
S, A, D, H, J, I D, E, J J S, A, I, D, H, J
D, E, H, I, F, S, D, E, H, I, F, S, G, B, C, D D, E, H, I, F, S, A, D, E, H, I, F, S,
A, C, J A, C, J C, J A, C, J

Problema 25

a) Construir la gramática libre de contexto generadora del siguiente lenguaje y estúdiese la

regularidad del mismo.
𝐿 = {0𝑚 1𝑛 | 𝑚, 𝑛 > 0, 𝑐𝑜𝑛 𝑚 𝑝𝑎𝑟 𝑦 𝑛 𝑖𝑚𝑝𝑎𝑟 ó 𝑣𝑖𝑐𝑒𝑣𝑒𝑟𝑠𝑎 }

b) Dada la siguiente gramática G en FNC, se pide calcular la correspondiente FNG considerando

el orden S < A < B < C. Igualmente, decidir la pertenencia de la palabra abbaa al lenguaje
generado por G, mediante el algoritmo CYK.

P = { S → AB | BC
A → AB | a
B → AA | CB | b
C→a|b
Inciso a)

G=(V, ∑, R, S) donde V={S1, S2}

∑={0, 1}
R= { S → S1 | S2
S1 → 0S11 | ε
S2 → 1S20 | ε }

Inciso b)

La FNG es la misma que la G en el problema 23 por lo que sólo se comprueba la pertenencia de

abba al lenguaje de G por CYK
 S, A, B
S, A, B S, A, B
S, A, B S, A, B S, A, B
S, A, B, C S, A, B, C S, A, B, C S, A, B, C
a b b a
La palabra si pertenece a L(G) por que en la última casilla tenemos al axioma.
Problema 26
a) Sea 𝐿 = {𝑎 𝑖𝑏 𝑗 𝑎 𝑗 𝑤 | 𝑤 𝑝𝑜𝑠𝑒𝑒 𝑖 𝑎 ′ 𝑠, 𝑖, 𝑗 ≥ 0 𝑚 }.Determínese una GLC que genere dicho lenguaje y
estudiar formalmente si es o no regular.
b) Simplificar la gramática siguiente y determinar su forma normal de Chomsky G=({S,

A, B, C, D, E, F}, {a, b}, P, S) dónde

P = { S → FaA | aAb | Bb A
→ CD | a | S
B → ACD | b
C → ε | AC
D → ε | aFE
E → bF | ε }
a)
G=(V, ∑, R, S) donde
V={S, A, B}
∑={a, b}
R= { S→A|B A → aAa | aAab | aAba | B | C B → bBa | ba | ε C → bC | b }

G no es regular porque tiene producciones del tipo A → aAa. L(G) tampoco es regular porque no existe un AF
que lo reconozca ya que al final de la cadena se deben de poner tantas a’s como a’s se hallan puesto al inicio,
y un AF no puede llevar la cuenta de las entradas.

b)
S → HA | IG | BG
A → CD | a | HA | IG | BG | KE | AF | AC
B → ACD | b | AD | AC | CD | a | HA | IG | BG| KE | AF | AC
C → AC | CD | a | HA | IG | BG | KE | AF | AC
D → KE | AF
E → GF
F → a G → b H → FF I → FA J → AC K → AF

Problema 27

Sea L el lenguaje sobre el alfabeto {a,b} siguiente:

𝐿 = {𝑎 𝑛 𝑏𝑚 𝑎 𝑛 𝑏 2𝑖 𝑤 | 𝑖 ≥ 0 , 𝑛 ≥ 1, 𝑚 𝑖𝑚𝑝𝑎𝑟 𝑦 𝑤 𝑡𝑖𝑒𝑛𝑒 𝑢𝑛 𝑛° 𝑝𝑎𝑟 𝑑𝑒 𝑎′𝑠}

a) Determina una GLC, G, tal que L(G) = L

b) Escribe un árbol de derivación en G para la palabra aabaab
c) Demuestra si L es o no regular
Problema 28

Dada la GLC G = ({S, A, B, C, D, E, F}, {a, b}, P, S) dónde

P={ S → bA | bAD | aB | aDE

A → bA | bAD | aC | aFE
B → bA | aDBB | aS | aFE | ε
C → bA | aDBB | aSD | aDE | ε
D → bCAF | aDA
E→b|a }
a) Determina L(G)
b) ¿Es G regular? ¿Y L(G)?
c) Calcula la FNC y la FNG de G.

𝐿 = {(𝑎∗𝑏∗)∗𝑎}
G si es regular ya que solo tiene producciones a su derecha. L(G) también es regular porque existe un AF que
lo reconoce

FNC
FNG
S → GA | GH | FB | FI | a S → bA | aB | a
A → GA | GH | FC | a A → bA | aC | a
B → GA | LM | FS | FK | FD B → bA | aS
C → GA | LM | FN | FI | FK | FD C → bA
D → FQ E→b|a
E→b|aF→a
G→b
H → AD
I → DE
K → DB
L → FD
M →BB
N → SD
0 → GC
Q → DA
Problema 29

a) Determinar una GLC que genere el siguiente lenguaje L= { w1a2j+1bjw2 / |w1|=i, |w2|=2i, i,j ≥0
}. Dar una derivación y un árbol de derivación para la palabra baaabab.
b) Determinar las formas normales de Chomsky y Greibach de la siguiente gramática
(manteniendo el orden de las variables y siguiendo los pasos explicados en clase) G= (
{X1,X2,X3}, {a,b}, P, X1) dónde P=
X1 → X2X1 | a
X2 → X1a | X2X2 | ε
X3 → X1b
a)

FNG
1. X2 → aX1’X3X2‘ | a X3X2‘ | aX2‘X3 | aX1’ X3
2. X2’ → aX1’X3X2‘X2‘ | a X3X2‘X2‘ | aX2‘X3X2‘ | aX1’X3X2‘ | aX1’X3X2‘ | aX3X2‘ | aX2‘X3 | aX1’X3
3. X1 → aX1’ | a
4. X1’ → aX2‘X1X1’ | aX1X1’ | aX2‘X1 | aX1

FNC
X → X2X1 | a
X1 → X2X1 | a
X2 → X1 X4 | X2X2
X3 → X1 X5
X4 → a
X5 → b
Problema 30

a) Constrúyase una GLC generadora del lenguaje L1 U L2 donde:

𝐿1 = {𝑎𝑖𝑏2𝑖 | 𝑖 ≥ 1}; 𝐿2 = {𝑏 𝑗𝑤𝑎𝑘 | |𝑤| = 𝑘 + 𝑗;𝑘, 𝑗 ≥ 0}. Estúdiese además la regularidad de dicho lenguaje.

b) Determinar, siguiendo los procedimientos vistos en clase, la FNC y la FNG de la siguiente

gramática:
G = ({S, A, B, C, D}, {a, b}, P, S) dónde
P = { S → AaC | DAa
A → Ab | CSa | Bb | ADb B
→ aSb | Caa
C→ε
D → CC | CD }

Nota: Para la FNG el orden de las variables es el orden en que aparecen.

a)
G1 = ({A, B}, {a, b}, P, S) dónde G2 = ({P, Q, T}, {a, b}, R, P) dónde
P = { A → aAbb | abb R = { P → QT
B → aAbb | abb } Q → bQ | bQa | ba | ab
T → bTa | aRa | ba | ab }

G = ({S, A, P, Q T}, {a, b}, U, S) dónde U = {

S→A|P
A → aAbb | abb
B → aAbb | abb
P → QT
Q → bQ | bQa | ba | ab
T → bTa | aRa | ba | ab }

El lenguaje no es regular porque tiene producciones del tipo A → aAbb con lo que no existe un AF que lo
pueda describir (ya que se tiene que llevar el conteo de las a’s para producir exactamente 2 b’s).

FNC
S → AE
A → AF | BF
B → EG | EE
E→a
F→b
G → SF
FNG
S → aSDDA1DCS2 | aCDA1DCS2 | aSDDDCS2 | aCDDCS2 | aSDDA1DCS1S2 | aCDA1DCS1S2 |
aSDDDCS1S2 | aCDDCS1S2 | aSDDCS1S2 | aCDCS1S2 | aSDDCS2 | aCDCS2 | aSDDA1DC | aCDA1DC |
aSDDDC | aCDDC | | aSDDA1DCS1 | aCDA1DCS1 | aSDDDCS1 | aCDDCS1 | aSDDCS1 | aCDCS1 |
aSDDC | aCDC
S2 → CDCS2 | CA1DCS2 | CDCS1S2 | CA1DCS1S2 | aSDDA1DC | aCDA1DC | aSDDDC| aCDDC | |
aSDDA1DCS1 | aCDA1DCS1 | aSDDDCS1 | aCDDCS1 | aSDDCS1 | aCDCS1| aSDDC | aCDC
A → aSDDCS1CA2 | aCDCS1CA2 | aSDDCCA2 | aCDCCA2 | aSDDCS1CA1A2 | aCDCS1CA1A2 |
aSDDCCA1A2 | aCDCCA1A2| aSDDA1A2 | aCDA1A2 | aSDDA2 | aCDA2 | aSDDCS1C | aCDCS1C |
aSDDCC | aCDCC | aSDDCS1CA1 | aCDCS1CA1 | aSDDCCA1 | aCDCCA1| aSDDA1 | aCDA1 | aSDD |
aCD
A2 → DCCA2 | DCS1CA2 | DCCA1A2 | DCS1CA1A2 | aSDDCS1C | aCDCS1C | aSDDCC| aCDCC |
aSDDCS1CA1 | aCDCS1CA1 | aSDDCCA1 | aCDCCA1| aSDDA1 | aCDA1 | aSDD | aCD

S1 → SCDC | SCA1DC | aSDDA1DC | aCDA1DC | aSDDDC | aCDDC | aSDDC | aCDC | aC

A1 → ADCC | ADCS1C | aSDDCS1 | aCDCS1 | aSDDC | aCDC | SC | aSDD | aCD | b
B → aSD | aC
C→a
D→b
Problema 31

Dada la siguiente GLC G= ([S, A, B, X, Y}, {a, b,c}, P, S) cuyas producciones son: P = { S
→ ASB | c
A → XaX
B → bX | ε
X → YbY
Y → aY | ε }

a) Determinar L(G)
b) Calcular la FNG
c) Demostrar por el algoritmo CYK y por algún otro método que la palabra acb ϵ L(G)

𝐿1 = {𝜔1 𝑝 𝑐 𝜔2 𝑞 | 𝜔1 = (𝑎 𝑖𝑏𝑎 𝑗𝑎𝑎 𝑘𝑏𝑎 𝑙) 𝑦 𝜔2 = ( 𝑏𝑎 𝑚 𝑏𝑎 𝑛 ∪ 𝑎𝑎 𝑜) 𝑐𝑜𝑛 𝑖, 𝑗, 𝑘, 𝑙, 𝑚, 𝑛, 𝑛, 𝑜 ≥ 0}

𝑐𝑜𝑛 𝑝 𝑦 𝑞 𝑖𝑔𝑢𝑎𝑙 𝑎𝑙 𝑛𝑜. 𝑑𝑒 𝑣𝑒𝑐𝑒𝑠 𝑞𝑢𝑒 𝑠𝑒 𝑟𝑒𝑝𝑖𝑡𝑒𝑛 𝑙𝑎𝑠 𝑐𝑎𝑑𝑒𝑛𝑎𝑠 𝜔,
𝑐𝑜𝑛 𝑐𝑎𝑑𝑎 𝑖𝑡𝑒𝑟𝑎𝑐𝑖ó𝑛 𝑙𝑎𝑠 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑖𝑛𝑡𝑒𝑟𝑛𝑎𝑠 𝑠𝑒 𝑟𝑒𝑠𝑒𝑡𝑒𝑎𝑛
FNG

S → aYDYCXSB | aDYCXSB | aYDCXSB |aDCXSB | bYCXSB | c| aYDYCXS | aDYCXS | aYDCXS | aDCXS |

bYCXS
A → aYDYCX | aDYCX| aYDCX | aDCX | bYCX
B → bX
X → aYDY | aDY | aYD| aD | bY | b
Y → aY | a
C→a
D→b

c)

Para su demostración se parte de la FNC:

S → GB | c | AS
A → EX
B → DX
X → FY | YD | DY | b
Y → CY | a
C→a
D→b

-
- -
C, Y, E S D, F, X
a c b

La palabra no pertenece a L(G) debido a queno se puede generar de ninguna de sus ramas
Problema 32

Dada la siguiente GLC G=({S, S1, S2, A, B}, {a, b}, P, S) siendo P = {
S → S1 | S2
S1 → a S1b | B
B → bB | b
S2 → a S2b | A A
→ aA | a

Se pide:
a) Determinar mediante el algoritmo CYK la pertenencia o no de la cadena aabbb a L(G)
b) Encontrar L(G)
c) Poner G en FNG siguiendo los pasos del algoritmo.

a)

FNC para el algoritmo CYK

S → CE | DB | b | CF | CA | a
S1 → CE | DB | b
B → DB | b
S2 → CF | CA | a
A → CA | a
C→a
D→b
E → S1D
F →S2D Al encontrar el axioma podemos asumir que la
cadena si pertenece a L(G)

b)
𝐿 = {𝑎𝑛 𝑏𝑚 | 𝑚 = 𝑛 + 𝑜, 𝑜 > 0; 𝑛 ≥ 1}
c)
FNG
S → aS1D | bB | b | aS2D | aA | a
S1 → aS1D | bB | b B → bB | b
S2 → aS2D | aA | a A → aA | a
C→a
D→b

Problema 34

a) Dado el lenguaje L siguiente sobre el alfabeto {a, b}:

𝐿2 = {𝑎𝑛 𝑏𝑎𝑚 𝑏 𝑝𝑎 | 𝑝 > 𝑚 + 𝑛; 𝑛 ≥ 1}

• Determinar una GLC G que genere L

• Demostrar si L y G son o no regulares
• Dar un árbol de derivación en G para la palabra abbba

b) Responder razonadamente, demostrando su veracidad o poniendo un contraejemplo que pruebe su

falsedad: para cualquier lenguaje regular L, ¿existe una GLC no regular g tal que L(G) = L?
c) Dada la GLC G=({S, A, B, C, F, G}, {a, b}, P, S) donde P
={ S → AB | BCB
A → FG | DE
C → BB | DaE | a
D → a | Ea | cD B
→ε
F→b
G→a }

Se pide calcular el lenguaje que genera, la FNC y la FNG sin que éstas tengan símbolos inútiles.
GLC G=({S, A, B, C, D}, {a, b}, R, S) donde
R = { S → aAa
A → aAb | B B → bC
C → aCb | D
D → bd | ε }

G no es regular por tener producciones mixtas S → aAa. L(G) tampoco es regular porque se debe de
mantener la relación de p=m+n lo que con un AF no se puede, sólo con un AP.

b)

FNC FNG
S → FG | a | ε S → bC | aE | cDE | a
A → FG A → bC | aE | cDE
C→a C →a
D → a | GD D → a | cD
F→b F→b
G→c

Problema 35

a) Dada la siguiente gramática G =({S, A, B, C}, {a, b}, P, S) donde P =

{ S → aSA | aB
A → CaC
B → bBa | ε
C → bC | ε }

Se pide calcular para ella:

• L(G)
• Un árbol de derivación y una derivación más a la izquierda para la palabra
aaaaabb
• La forma normal de Greibach

b) Determinar una GLC G tal que L(G) = L siendo L:

𝐿 = {𝑎 𝑚 𝑏𝑛 | 𝑛 = 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 2 𝑦 𝑚 ≠ 𝑚ú𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 2 𝑜 𝑣𝑖𝑐𝑒𝑣𝑒𝑟𝑠𝑎}

Asimismo, demuéstrese formalmente la regularidad o no de G y de L.

 𝐿 = {𝑎 𝑖 𝑏 𝑗 𝑎 𝑗𝜔1 | 𝑖 ≥ 1, 𝑗 ≥ 0, 𝜔1 = (𝑏𝑛 𝑎𝑏 𝑚 )𝑖, 𝑛, 𝑚 ≥ 0 𝑐𝑎𝑑𝑎 𝑖𝑡𝑒𝑟𝑎𝑐𝑖ó𝑛 𝑑𝑒 𝑖 𝑒𝑛 𝜔1 𝑠𝑒 𝑟𝑒𝑠𝑒𝑡𝑒𝑎𝑛 𝑛 𝑦 𝑚 }

S → aSA → aaaaA
→ aaSAA → aaaaCaC
→ aaaBAA → aaaaaC
→ aaaAA → aaaaabC
→ aaaCaCA → aaaaabbC
→ aaaaCA → aaaaabb

b)

Problema 36

a) Dada la siguiente gramática G=({S, A,B}, {a, b}, P, S), donde: P =

{ S → aA
A → BAa | B
B → bB | b}
Se pide calcular para ella:
• L(G)
• Un árbol de derivación y una derivación más a la derecha para la palabra abba
• La forma normal de Chomsky y la forma normal de Greibach
• Aplicar el algoritmo CYK para demostrar que la palabra abba pertenece a L(G)
• Determinar, en base a los cálculos realizados en dicho algoritmo, las subcadenas de esa
palabra que pertenecerían a L(G) si el símbolo inicial fuese el A.

b) Sea L el lenguaje sobre el alfabeto {a, b, c} definido por:

𝐿 = {𝜔1 𝑐 𝜔2 | 𝜔1 , 𝜔2 𝜖 {𝑎, 𝑏}∗ 𝑦 𝑒𝑙 𝑛° 𝑑𝑒 𝑎 ′ 𝑠 𝑑𝑒 𝜔1 𝑐𝑜𝑖𝑛𝑐𝑖𝑑𝑒 𝑐𝑜𝑛 𝑒𝑙 𝑛° 𝑑𝑒 𝑏′ 𝑠𝑑𝑒 𝜔2 }

Se pide demostrar formalmente que L es un Lenguaje Libre de Contexto y que no existe ningún
AFD que lo reconozca.
 𝐿 = {𝑎𝑖 𝑏𝑗 𝑎𝑘 | 𝑖, 𝑗 > 0, 𝑘 ≥ 0}

Derivación más a la derecha

S → aA
→ aBAa
→ aBba
→ abba

FNC FNG
S → CA S → aA
A → BD | EB | b A → bBD | bD | bB | b
B → EB | b B → bB | b
C→a C→a
D → AC D → bBDC | bDC | bBC | bC
E→b
E→b

S
S bbb
A
S bb bb
A, B A, B
C, D b b C, D
A, B, E A, B, E
a b b a
b)
L es un LLC por que existe una GLC que lo genera: G=({S, A,B}, {a, b}, P,
S), donde:
P={ S→A
A → aAb | bAa | c | bA | Aa }

Y no existe ningún AFD que lo genere poque se necesita un contador que lleve la cuenta del número de a’s en w1 para poner
el mismo número de b’s en w2.

Problema 37

Dada la siguiente gramática G={{S,A,B,X,Y,Z,T}.{a,b}, P, S} dónde P={

S → AX
A → BbB
B → aBa | aa
X → bY | Z
Y → bX
Z → aT | ε
T → aZ }

a) Calcular L(G).
b) Demostrar formalmente si G y L(G) son o no regulares.
c) La forma normal de Chomsky.
d) Demostrar que la palabra “aabaa” pertenece a L(G) por 3 métodos: el algoritmo CYK, una
derivación a la derecha y un árbol de derivación.

𝐿(𝐺) = { 𝑎2𝑖 𝑏𝑎2𝑗 𝑏𝑘𝑎𝑙 con i, j ≥ 1 y k, l ≥ 0}

b)
La gramática G no es regular porque no cumple con la forma S→aT para ser regular por la izquierda ni T→Sb
para ser regular por la derecha, e incluso las convina (que en una G regular no puede pasar).
L(G) si es regular porque puede ser descrito por un AF que lo reconozca

c)
S0 → AX | EB
S → AX | EB
A → EB
B → C | CC
X → DY
Y → DX
Z → CT | a
T → CZ | a
C→a
D→b
E → BD
F → CB
Problema 38

Dada la GLC G={{S,A,B,C,D}.{a,b,d}, P , S} siendo P= {

S → AbaC
A → AB | a
B→b|εC
→D|ε
D→d }

Se pide:

a) Determinar el lenguaje generado por G

b) Estudiar formalmente la regularidad de G y de L(G)
c) Calcular las formas de Chomsky y Greibach de G (en este último caso el orden de las variables
es S < A < B < C < D
d) Dar un árbol de derivación en G para la palabra abba

𝐿(𝐺) = { 𝑎𝑖 𝑏𝑗𝑏𝑎𝑑𝑘 con i ≥ 1, j ≥ 0 y 0 ≤ k ≤ 1}

La gramática G no es regular porque no cumple con la forma S→aT para ser regular por la izquierda ni T→Sb
para ser regular por la derecha, e incluso las convina (que en una G regular no puede pasar).

L(G) si es regular porque puede ser descrito por un AF que lo reconoce.

c)

FNC FNG
S0 → AF | AD
S → AF | AD S → aBBDC | aBBD | aABBDC | aABBD | aBDC | aBD
A → AB | a A → aB | aAB | a
B→b B→b
C→d C→d
D→ BE D→a
E→ a
F→ DC

d)
Problema 39

Sea G = ({S, A, B}, {a,b}, P, S) una GLC cuyas producciones son: P =

{S → aSaA | BA
A→a|b
B → bBb | b }

1. Determinar L(G)
2. Estudiar la regularidad de G y de L(G)
3. Comprobar que abaab ϵ L(G) utilizando una derivación más a la derecha, un árbol de
derivación y el algoritmo CYK.

𝐿(𝐺) = { 𝑎 𝑖𝜔1 𝑖| 𝑏 𝑗 (𝑎 ∪ 𝑏)} 𝑐𝑜𝑛 𝑖, 𝑗 ≥ 0 , 𝜔1 = 𝑏 𝑗 (𝑎 ∪ 𝑏) 𝑐𝑎𝑑𝑎 𝑞𝑢𝑒 𝑠𝑒 𝑟𝑒𝑝𝑖𝑡𝑒 𝑢𝑛𝑎 𝜔1 𝑠𝑒 𝑠𝑖𝑔𝑢𝑒 𝑙𝑎 𝑠𝑒𝑟𝑖𝑒 𝑎𝜔1𝑎𝜔1 … (𝑎 ∪
𝑏) 𝑦 𝑠𝑒 𝑟𝑒𝑖𝑛𝑖𝑐𝑖𝑎 𝑗

b )G no es regular porque tienen producciones del tipo B → bBb. L(G) tampoco es regular porque no hay un AF
que lo describa.

c ) Derivación más a la derecha

S → aSaA
→ aSab
→ aBAab
→ aBaab
→ abaab