Soluciones a los exámenes de Junio 2022

Autómatas, Gramáticas y Lenguajes

(1◦ curso)

Grado en Ingeniería Informática y Grado en Ingeniería de las

Tecnologías de la Información

Elena Gaudioso Vázquez y Félix Hernández del Olmo

Plantillas de respuestas
Nacional 1a Semana

• Tipo A:
(1). a (2). c (3). b (4). c (5). b (6). a (7). d (8). d (9). c (10). d
• Tipo B:
(1). a (2). c (3). d (4). d (5). b (6). b (7). c (8). c (9). d (10). a
• Tipo C:
(1). a (2). c (3). b (4). a (5). b (6). d (7). c (8). d (9). d (10).c

Nacional-UE 2a Semana

• Tipo A:
(1). d (2). b (3).c (4).b (5).c (6).c (7).c (8).d (9).d (10).a
• Tipo B:
(1). d (2).b (3).c (4).d (5).c (6).c (7).b (8).d (9).a (10).c
• Tipo C:
(1). c (2).d (3).c (4).d (5).c (6).d (7).b (8).a (9).c (10).b

1
Nacional 1a Semana
1 Dado el alfabeto Σ = {0, 1} sea L el lenguaje definido mediante la siguiente
expresión regular: (0 + 1)∗ 00(0 + 1)∗ . Indicar cuál de las siguientes afirmaciones es
verdadera:
(a). L es un lenguaje independiente del contexto no regular.
(b). Todas las cadenas pertenecientes al lenguaje L únicamente tienen dos ceros.
(c). Todas las cadenas pertenecientes al lenguaje L tienen al menos dos ceros consecutivos.
(d). Ninguna de las anteriores afirmaciones es verdadera.
Solución: C. La opción A es falsa puesto que una expresión regular siempre representa un
lenguaje regular. La opción B es falsa puesto que las cadenas pertenecientes al lenguaje L
pueden tener más de dos ceros, por ejemplo, 0001 ∈ L. La opción C es verdadera puesto
que todas las cadenas de L siempre contienen la subcadena 00.
2 Sea G = ({S, A, B, C}, {a, b}, S, P ) donde S es el símbolo inicial de la gramática y
P es el siguiente conjunto de producciones:
S → A|B
A → aB|bS|b
B → AB|Ba|CC
C → AS|b|ǫ
Indicar cuál de las siguientes afirmaciones es verdadera:
(a). G es una gramática regular.
(b). Es cierto que aaab ∈ L(G)
(c). L(G) es un lenguaje recursivamente enumerable no independiente del contexto.
(d). Ninguna de las anteriores afirmaciones es verdadera.
Solución: B. La opción A es falsa puesto que las producciones de la gramática no cumplen
con las restricciones de una gramática regular. La opción B es verdadera teniendo en cuenta
S→B B→AB A→aB B→Ba B→CC
la siguiente derivación: S −−−→ B −−−−→ AB −−−−→ aBB −−−−→ aBaB −−−−→
C→ǫ C→ǫ B→AB A→aB B→CC C→b
aCCaB −−→ aCaB −−→ aaB −−−−→ aaAB −−−−→ aaaBB −−−−→ aaaCCB −−−→
C→ǫ B→CC C→ǫ C→ǫ
aaabCB −−→ aaabB −−−−→ aaabCC −−→ aaabC −−→ aaab. La opción C es falsa
puesto que G es una gramática independiente del contexto y por tanto L(G) es al menos, un
lenguaje independiente del contexto.

2
3 Dado el alfabeto Σ = {0, 1}, sea L el lenguaje al que pertenecen todas las cadenas que
contienen al menos tres 0’s que pueden ser o no consecutivos. Indicar cuál de las
siguientes afirmaciones es verdadera:

(a). L se puede representar mediante la siguiente expresión regular: (0 + 1)∗ 0∗

(b). L se puede representar mediante la siguiente expresión regular:

(0 + 1)∗ 0(0 + 1)∗ 0(0 + 1)∗

(c). L se puede representar mediante la siguiente expresión regular: 0∗ 1∗

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: D. La opción A es falsa puesto que la expresión regular (0 + 1)∗ 0∗ puede generar
cadenas con menos de tres ceros, en particular la cadena vacía. La opción B es falsa puesto
que la expresión regular (0 + 1)∗ 0(0 + 1)∗ 0(0 + 1)∗ puede generar cadenas con menos de
tres ceros, por ejemplo, la cadena 00. La opción C es falsa puesto que la expresión regular
0∗ 1∗ puede generar cadenas con menos de tres ceros, en particular la cadena vacía.

4 Dado el alfabeto Σ = {a, b}, sea L(G) el lenguaje que deriva la gramática G definida a
continuación:

G = ({S, A}, Σ, S, P )

donde S es el símbolo inicial de la gramática y P es el siguiente conjunto de producciones:

S → aaSA
S → aab
A → bA
A→b

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L(G) se puede definir mediante la siguiente expresión regular:

(ǫ + ((aa)(aa)∗bb∗ ))

(b). L(G) se puede definir de la siguiente manera: L(G) = {(aa)n bn : n ≥ 0}

(c). L(G) se puede definir de la siguiente manera:

L(G) = {(aa)n bm : m ≥ n, n > 0, m > 0}

(d). Ninguna de las anteriores afirmaciones es verdadera.

3
Solución: D. La opción A es falsa puesto que L(G) es independiente del contexto no
regular y la expresión regular genera cadenas que no se pueden derivar con la gramática
(por ejemplo, la cadena vacía o la cadena aa). La opción B es falsa puesto que la gramática
puede generar cadenas con más b’s que pares aa, por ejemplo la cadena aaaabbb. Para ver el
lenguaje que deriva la gramática G, hay que ver cómo son las derivaciones a partir del
símbolo inicial S. Cada vez que se deriva el símbolo S se introduce el par aa y los no
terminales S y A en la forma sentencial. Puesto que el no terminal A deriva a su vez b’s o
bA, el número de b’s siempre será mayor o igual al número de pares aa. No obstante, S
deriva también la cadena aab. Por tanto, cada vez que se deriva S la derivación terminará
derivando la subcadena aab. No es, por tanto, posible derivar cadenas de la forma aabb o
aabbb (esto es cadenas de la forma (aa)bm ) que sí están en el lenguaje de la opción C
considerando n = 1 y m ≥ n. Por consiguiente, la opción C es falsa.
5 Dado el alfabeto Σ = {a, b, c}, sea L1 el lenguaje que representa la expresión regular
cb∗ (a∗ b)∗ y L2 el lenguaje que representa la expresión regular c(b + aa∗ b)∗ . Indicar
cuál de las siguientes afirmaciones es verdadera:
(a). L1 = L2
(b). Existe al menos una cadena que pertenece a L1 y que no pertenece a L2
(c). Existe al menos una cadena que pertenece a L2 y que no pertenece a L1
(d). Ninguna de las anteriores afirmaciones es verdadera.
Solución: A. El lenguaje L1 contiene cadenas que empiezan por un símbolo c seguida de
cero o más b’s y terminadas en cero o más veces la expresión a∗ b (cadenas con cero o más
a’s terminadas en b). El lenguaje L2 genera cadenas que empiezan por c seguidas por cero o
más b’s o por una o más a’s y terminadas en b. Por tanto, ambos lenguajes contienen
cadenas que empiezan por c seguidas de cero o más b’s, cero o más a’s seguidas de una o
más b’s. El lenguaje que generan ambas expresiones se podrían representar mediante el
siguiente autómata:
M = ({p, q, r}, {a, b, c}, δ, p, {q})
donde la función de transición δ se define mediante el siguiente diagrama de transiciones:
b a
a
p c q r
b

4
Las dos expresiones son, por tanto, equivalentes. Por consiguiente, la opción A es verdadera
y las opciones B y C son falsas.

6 Dado el alfabeto Σ = {a, b, c}, sea L el lenguaje definido a continuación:

L = {ai bj ci+j : i, j > 1, (i + j) es impar}

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L es un lenguaje regular.

(b). L es un lenguaje recursivamente enumerable no independiente del contexto.

(c). L es un lenguaje independiente del contexto no regular.

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: C. La opción A es falsa puesto que es necesaria una pila para llevar la cuenta de
cuántos símbolos a y b se leen para posteriormente leer un número de c’s que coincida con
la suma de a’s y b’s leídas. Para comprobar que esta suma es impar se puede realizar
mediante estados. Se deja como ejercicio la definición de un autómata a pila que reconozca
L (será similar al mostrado en el ejercicio 8 de la práctica 1 del curso 2021-2022).

7 Dado el alfabeto Σ = {a, b, c}, sea L el lenguaje definido a continuación:

L = {an bm cn bn+m : n > 0, m > 0}

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L es regular.

(b). L es independiente del contexto no regular.

(c). L es recursivamente enumerable no independiente del contexto.

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: C. Una única pila no es suficiente puesto que para comprobar que se leen el
mismo número de a’s que de c’s se desapilaría el número de a’s para comprobar que se lee
el mismo número de c’s y ya no se podría comprobar que se lee un número de b’s igual a la
suma de a’s y b’s.

5
8 Sea M una máquina de Turing de varias cintas, indicar cuál de las siguientes
afirmaciones es FALSA:

(a). Independientemente de la definición de M , siempre existe un autómata finito

determinista que acepta L(M ).

(b). Siempre es posible definir una máquina de Turing de una única cinta que acepta
L(M ).

(c). Siempre se cumple que L(M ) es un lenguaje recursivamente enumerable.

(d). Siempre es posible definir una máquina de Turing no determinista que acepta L(M ).

Solución: A. Existen lenguajes reconocidos por máquinas de Turing que son

recursivamente enumerables no independientes del contexto y por tanto no regulares (por
ejemplo, el lenguaje {xn y n z n : n > 0}). Las opciones B,C y D son verdaderas por la propia
definición de una máquina de Turing y por la equivalencia entre máquinas de Turing
deterministas, no deterministas, de una cinta y de varias cintas.

9 Sea L1 un lenguaje regular y L2 un lenguaje independiente del contexto. Indicar cuál de

las siguientes afirmaciones es VERDADERA:

(a). L1 ∪ L2 siempre es un lenguaje regular.

(b). L1 ∪ L2 siempre es un lenguaje independiente del contexto.

(c). Siempre se cumple que L1 ⊂ L2

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: B. La opción A es falsa puesto que si L2 es independiente del contexto no

regular, puede ocurrir que L1 ∪ L2 sea no regular (por ejemplo: L1 = {xn : n > 0} y
L2 = {xn y n : n > 0}). La opción B es verdadera por las propiedades de los lenguajes
independientes del contexto. La opción C es falsa puesto que dependerá de la propia
definición de los lenguajes L1 y L2 (si se toma el ejemplo anterior esta condición no se
cumpliría).

10 Dado el alfabeto Σ = {a, b, x, d}, sea M el autómata a pila que se define de la

siguiente manera: M = ({p, q, r, s, t, u, v}, Σ, Γ, δ, p, Z0 , {v}) donde el conjunto de
símbolos de pila es Γ = {a, Z0 } y la función de transición δ se define mediante el
siguiente diagrama de transiciones:

6
 t

d, ǫ; ǫ x, a; ǫ
a, ǫ; a x, a; ǫ

ǫ, ǫ; Z0 a, ǫ; a
p q r u v
ǫ, Z0 ; ǫ
b, ǫ; ǫ

b, ǫ; ǫ x, a; ǫ
s

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L(M ) es regular.

(b). M es un autómata a pila no determinista.

(c). L(M ) = L donde L = {an bm xn : n ≥ 1, m ≥ 1}

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: D. La opción A es falsa puesto que

L(M) = {an bm xn , n, m > 0} ∪ {an dxn , n > 0} que es un lenguaje independiente del
contexto no regular. La opción B es falsa puesto que M es un autómata a pila determinista.
La opción C es falsa puesto que, por ejemplo, el autómata acepta la cadena adx que no está
contenida en el lenguaje L.

Nacional-UE 2a Semana
11 Sea G la gramática definida de la siguiente manera:

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

donde S es el símbolo inicial de la gramática y P es el siguiente conjunto de producciones:

7
 S → AB
A → aAb
A → aA
A→ǫ
B → Bc
B→ǫ

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). G es una gramática regular.

(b). L(G) es un lenguaje independiente del contexto no regular.

(c). L(G) puede representarse mediante la expresión regular a∗ b∗ c∗

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: B. La opción A es falsa puesto que la gramática G es una gramática no regular.

La gramática G deriva cadenas que resultan de la concatenación de las subcadenas que
deriva el no terminal A y el no terminal B. El no terminal B deriva cadenas de cero o más
c’s. Por su parte, el no terminal A deriva cadenas de a’s seguidas de b’s cumpliendo que el
número de a’s es mayor o igual que el número de b’s (también derivaría la cadena vacía).
Por tanto, L(G) se podría definir de la siguiente manera:
L(G) = {an bm cp : n ≥ 0, m ≥ 0, p ≥ 0 y n ≥ m}. Este lenguaje es independiente del
contexto no regular. La opción C es falsa puesto que el lenguaje de esa expresión sería
regular (además derivaría la cadena abbbc que no deriva la gramática).

12 Sea G la gramática definida de la siguiente manera:

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

donde S es el símbolo inicial de la gramática y P es el siguiente conjunto de producciones:

S → Ba|Ab
A → Sa|AAb|a
B → Sb|BBa|b

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). No es posible definir una gramática en Forma Normal de Chomsky equivalente a G.

8
 (b). G en una gramática regular.

(c). La longitud mínima de las cadenas pertenecientes a L(G) es 2.

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: C. La opción A es falsa puesto que la gramática no deriva la cadena vacía. La

opción B es falsa puesto que G no es una gramática regular. Las cadenas de menor longitud
que se pueden derivar de G son las cadenas: ba y ab y por tanto, la opción C es verdadera.
13 Dado el alfabeto Σ = {a, b}, sea L el lenguaje definido de la siguiente manera:

L = {an bm : n > 0, m > 0, n es par y m es impar }

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L es regular.

(b). L es independiente del contexto no regular.

(c). L es recursivamente enumerable no independiente del contexto.

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: A. L puede definirse como la intersección de dos lenguajes regulares: L1 y L2

donde L1 y L2 se definen de la siguiente manera:

L1 = {an bm : n es par }
L2 = {an bm : m es impar }

y puede representarse mediante la expresión regular aa(aa)∗ b(bb)∗

14 Dado el alfabeto Σ = {0, 1}, sea L el lenguaje al que pertenecen todas las cadenas
que contienen como máximo tres símbolos 0’s que pueden ser o no consecutivos.
Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L puede representarse mediante la siguiente expresión regular: 1∗ 01∗ 01∗ 01∗

(b). L puede representarse mediante la siguiente expresión regular:

(0 + 1)∗ 000(0 + 1)∗

(c). L puede representarse mediante la siguiente expresión regular

(0 + 1)∗ 0(0 + 1)∗ 0(0 + 1)∗

9
 (d). Ninguna de las anteriores afirmaciones es verdadera

Solución: D. La opción A es falsa puesto que el lenguaje que representa esa expresión
regular contiene únicamente las cadenas con exactamente tres ceros que pueden ser o no
consecutivos (no incluye las cadenas con menos de tres ceros). La opción B es falsa puesto
que esa expresión regular puede derivar cadenas con más de tres ceros (además, al menos
tres ceros deben ser consecutivos). La opción C es falsa puesto que deriva cadenas con más
de tres ceros (como por ejemplo la cadena 00000).

15 Dado el alfabeto Σ = {a, b, c}, sea G la gramática definida a continuación:

G = ({S, A}, Σ, S, P )

donde S es el símbolo inicial de la gramática y P es el siguiente conjunto de producciones:

S → aS
S → bS
S→A
A → cA
A→c
A→S

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). Todas las cadenas contenidas en L(G) tienen al menos un símbolo b y un símbolo a.

(b). G es una gramática regular.

(c). L(G) se puede representar mediante la expresión regular: aa∗ bb∗ cc∗

(d). Ninguna de las anteriores afirmaciones es verdadera

Solución: D. La opción A es falsa puesto que la gramática deriva la cadena c. La opción B

es falsa puesto que G no es una gramática regular (las producciones tercera y la sexta no
cumplen con las restricciones de una gramática regular). La opción C es falsa puesto que la
gramática puede derivar cadenas que no contengan a’s o b’s y además no se impone que las
a’s deban estar antes que las b’s.

16 Dado el alfabeto Σ = {a, b, c, d}, sea L el lenguaje definido a continuación:

L = {(ab)n bm (cd)n+m : n > 0, m > 0}

10
Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L es regular.

(b). L es independiente del contexto no regular.

(c). L es recursivamente enumerable no independiente del contexto.

(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: B. La opción A es falsa puesto que es necesaria una pila para comprobar cuantos
pares ab y símbolos b se leen para leer el mismo número de pares cd. Puesto que es
suficiente una única pila, L es independiente del contexto no regular.

17 Dado el alfabeto Σ = {a, b}, sean M1 y M2 dos autómatas finitos definidos de la

siguiente manera: M1 = ({p, q, r, s, t, u}, Σ, δ1 , p, {p, s, t}) donde la función de
transición δ1 se define mediante el siguiente diagrama de transiciones:
b
q s
b
b
p a
a
a
r a u
t
a
y M2 = ({q0 , q1 , q2 , q3 }, Σ, δ2 , q0 , {q0 , q3 }) donde la función de transición δ2 se
define mediante el siguiente diagrama de transiciones:
a
q1 q3
a a
q0
b

b q2

Indicar cuál de las siguientes afirmaciones es verdadera:

11
 (a). L(M1 ) = L(M2 )

(b). L(M1 ) ⊂ L(M2 )

(c). L(M2 ) ⊂ L(M1 )

(d). Ninguna de las anteriores afirmaciones es verdadera

Solución: D. Existen cadenas de L(M1 ) que no están en L(M2 ) (como por ejemplo la
cadena bba) y viceversa (como por ejemplo la cadena bbaa)

18 Sea M una máquina de Turing determinista. Indicar cuál de las siguientes afirmaciones
es verdadera:

(a). M sólo puede desplazarse hacia la derecha en la cinta

(b). M no puede hacer operaciones de escritura en la cinta

(c). M puede desplazarse hacia la derecha, hacia la izquierda y realizar operaciones de

lectura y escritura en la cinta

(d). Ninguna de las anteriores afirmaciones es verdadera

Solución: C. Por la definición de una máquina de Turing.

19 Dado el alfabeto Σ = {a, b, c, d}, sea M el autómata a pila definido a continuación:

M = ({q0 , q1 , q2 , q3 }, Σ, Γ, δ, q0 , Z0 , {q3 })

donde Γ = {a, b, c, d, S, A, Z0 } es el conjunto de símbolos de pila y la función de

transición δ se define mediante el siguiente diagrama de transiciones:
ǫ, S; abSdc
ǫ, S; A
ǫ, A; cdAba
ǫ, A; ǫ
a, a; ǫ
b, b; ǫ
c, c; ǫ
d, d; ǫ

ǫ, ǫ; Z0 ǫ, ǫ; S ǫ, Z0 ; ǫ
q0 q1 q2 q3

12
Indicar cuál de las siguientes afirmaciones es verdadera:

(a). M es un autómata a pila determinista.

(b). L(M ) es un lenguaje regular.
(c). L(M ) puede definirse de la siguiente manera:
L(M ) = {(ab)n (cd)m(ba)m (dc)n : n ≥ 0, m ≥ 0}
(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: C. El autómata es equivalente a la gramática independiente del contexto definida

a continuación (según el procedimiento 7.4 del libro):

G = ({S, A}, {a, b, c, d}, S, P )

donde S es el símbolo inicial de la gramática y P es el siguiente conjunto de producciones:

S → abSdc
S→A
A → cdAba
A→ǫ

20 Dado el alfabeto Σ = {a, b, c} sea L el lenguaje definido de la siguiente manera:

L = {an bp cn+1 : p ≥ n, n ≥ 0}

Indicar cuál de las siguientes afirmaciones es verdadera:

(a). L es regular.
(b). L es independiente del contexto no regular.
(c). L es recursivamente enumerable no independiente del contexto.
(d). Ninguna de las anteriores afirmaciones es verdadera.

Solución: C. La opción A es falsa puesto que es necesario llevar la cuenta del número de
a’s, b’s y c’s se han leído para comprobar que se lee una c más que el número de a’s y que el
número de b’s es mayor que el número de a’s. Un autómata a pila no será suficiente puesto
que si se comprueba que el número de b’s es mayor que el número de a’s entonces ya no se
tendría información del número de a’s para comprobar el número de c’s.

13