ejercicios Tema4 UC3M TALF SANCHIS LEDEZMA IGLESIAS GARCIA ALONSO

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes y Gramáticas


 
Teoría
 de
 Autómatas
 y
 
Lenguajes
 Formales
 
Ejercicios
 de
 
Lenguajes y Gramáticas
 

Autores:
Araceli Sanchis de Miguel
Agapito Ledezma Espino
Jose A. Iglesias Martínez
Beatriz García Jiménez
Juan Manuel Alonso Weber

* Algunos ejercicios están basados en enunciados de los siguienteslibros:
• Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón
Salomón. Teoría de autómatas y lenguajes formales. McGraw-Hill (2007).
• Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga. Teoría de lenguajes,
gramáticas y autómatas. Publicaciones R.A.E.C. (1997).
• Pedro Isasi, Paloma Martínez y Daniel Borrajo. Lenguajes, Gramáticas y
Autómatas. Un enfoque práctico. Addison-Wesley(1997).

1

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes y Gramáticas

1. Crear una gramática que genere los siguientes lenguajes:
a)
b)
c)
d)
a)
b)
c)
d)

{ a, aa, aaa }
{ a, aa, aaa, aaaa, aaaaa, …)
{ λ, a, aa, aaa }
{ λ, a, aa, aaa, aaaa, aaaaa, …)
La notación empleada para representar cada uno de los lenguajes será:
{ an | n ∈ [1, 3] }
{ an | n > 0 }
{ an | n ∈ [0, 3] }
{an | n ≥ 0 }

2. Dadas las gramáticas G=(ΣT, ΣNT, S, Pi} donde:
G1
ΣT = {c}
ΣNT = {S, A}
P1: S→λ⏐A
A→AA| c

G2
ΣT = {c,d}
ΣNT = {S, A}
P2: S→λ⏐A
A→cAd| cd

G3
ΣT = {c}
ΣNT = {S, A}
P3: S→λ⏐A
A→AcA| c

G4
G5
ΣT = {c,d}
ΣT = {c,d}
ΣNT = {S, A,T}
ΣNT = {S, A}
P4: S→cA
P5: S→λ⏐A
A→d | cA| Td
A→Ad| cA | c| d
T→Td | d

Determinar el lenguaje asociado a dichas gramáticas.
3. Determinar el tipo de lassiguientes gramáticas en la jerarquía de Chomsky,
justificándolo:
a) G=({a,b}, {A,B,S}, S, P),
P={S::=aA, A::=bB, A::=aA, A::=a, B::=λ}
b) G=({a,b,c}, {A,B,C,S}, S, P),
P={S::=aAb, S::=Ba, S::=λ, aAbC::=aAbB, aAbC::=aabC, BCc::=AaCc,
BCc::=BaAbc, C::=Ca, C::=a}
c) G=({casa, jardin, gato}, {S, CASERON, BOSQUE, TIGRE}, S, P),
P={ S::=TIGRE jardin, S::=BOSQUE CASERON, BOSQUE::=λ,
jardin CASERON TIGREcasa::=jardin BOSQUE TIGRE casa,
gato CASERON BOSQUE::=gato BOSQUE casa TIGRE BOSQUE,
BOSQUE::=TIGRE casa, BOSQUE::=jardin
}
d) G=({x,y}, {C,A,B,S}, S, P),
P={S::=Cx, S::=Cy, S::=By, S::=Ax, S::=x, S::=y, A::=Ax, A::=Cx, A::=x,
B::=By, B::=yA, C::=xA}
e) G=({a,b,c}, {S,B}, S, P),
P={S::=abc, S::=aBSc, Ba::=aB, Bb::=bb}

2

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes yGramáticas

4. Dada la gramática G, se pide:
G=({a,b,c}, {S,A,B}, S, P), P={S::=λ, S::=aAc, A::=aA, A::=Ac, A::=B, B::=b, B::=Bb}
a)
b)
c)
d)

Especificar el tipo de G en la jerarquía de Chomsky, razonadamente.
Determinar el lenguaje L generado por la gramática G.
Construir 2 árboles de derivación para una misma palabra perteneciente a L(G).
Comprobar si las siguientes formas sentenciales son válidasen G, y en caso
afirmativo establecer una cadena de derivaciones que permite llegar a cada una de
ellas.
d.1.- aaAcc
d.2.-ac
d.3.-ababBcc
d.4.-abbccc

5. Obtener una gramática de tipo 0 para el lenguaje L={anbncn / n≥1}.
6. Realizar las transformaciones necesarias del proceso de limpieza de gramáticas, para
obtener una gramática limpia G' equivalente a la G dada.
G = ({a,b,c,d}, {X,Y,Z,O,P,Q,A}, Z,P),
P = { Z::=Z, Q::=OP, X::=aa, Z::=aX, Y::=aa, Z::=Ya, O::=b, Z::=aaa,
P::=QO, Q::=d, P::=c, O::=PQ}
7. Dada la gramática G LI, obtener una G’ LD equivalente.
G=({0,1},{A,S},S,P)
P={ S ::= 1 | A1; A ::= S0}
8. Dada la gramática G:
G = ({e,f,g,z,a,b,d}, {Y, X, E, A, D, I, G}, A, P),
P = { A::=a
E::=b
A::=azb
A::=aX
E::=E
G::=g
X::=XE
D::=eI
X::=z
Y::=b
I::=fG
X::=Xb
E::=d }
a) Transformar a FNC,explicando cada paso realizado.
b) Determinar si las palabras 'abz' y 'azdbb' pertenecen al lenguaje generado por G. En
caso afirmativo, generar un árbol de derivación para dicha palabra. En caso
negativo, justificar la no pertenencia.
3

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes y Gramáticas

9. Obtener una gramática en FNC equivalente a la siguiente:
G = ({a, b,...