ETSINF TAL Examen Final 02/02/2023

Primer Parcial
(Justifique formalmente las respuestas o proporcione resultados parciales)

Ejercicio 1 (2 puntos)
Dados el siguiente lenguaje y homomorfismo:
(
h(0) = aa
L = {an bm : n mód 2 = m mód 2}
h(1) = b

(a) Enumere las 8 primeras palabras en orden canonico de L

Solución:
λ, aa, ab, bb, aaaa, aaab, aabb, abbb

(b) Describa el lenguaje (ab)−1 L.

Solución:
(ab)−1 L = {bn : n mód 2 = 0}

(c) Describa el lenguaje P ref (L).

Solución:
P ref (L) = {an bm : n, m ≥ 0}

(d) Describa el lenguaje h−1 (L).

Solución:
h−1 (L) = {0n 1m : n ≥ 0 ∧ m mód 2 = 0}

Ejercicio 2 (1 punto)
Describa el lenguaje aceptado por el siguiente autómata:
a, b a, b

b b

Solución:
L = {x ∈ {a, b}∗ : b ∈ Suf (x) ∧ |x|b ≥ 2}

Ejercicio 3 (3 puntos)
Proporcione AFD para los lenguajes:
(a) L = {an bm : n mód 2 = m mód 2}
ETSINF TAL Examen Final 02/02/2023

Solución:

a b
b Ia /Ib Ia /Pb
Pa Pa
a b
b
b
Pa /Ib Pa /Pb
b

Nombramos cada estado con información acerca del número (par o impar) de
sı́mbolos a y b analizados. Notamos que han de aceptarse palabras formadas por
una secuencia de sı́mbolos a seguida por una de sı́mbolos b.

(b) L = {x ∈ {a, b}∗ : |x|a mód 2 = 0 ∨ ba ∈ Suf (x)}

Solución:
a
b

Pa /− b Pa /b a Ia /ba

a a b b

Ia /− Ia /b a Pa /ba
b

a b

El nombre de cada estado indica el número (par o impar) de sı́mbolos a que se

han procesado y el fragmento de sufijo ba que se ha procesado.

Ejercicio 4 (21/2 puntos)

Obtener un AFD equivalente al siguiente autómata:
a b

q1 a q2 λ q3 a q4

b
λ λ
q5 b

Solución:
Aplicando los algoritmos vistos en clase, se obtiene el siguiente autómata:
ETSINF TAL Examen Final 02/02/2023

a b
→ {1} {1, 2, 3, 5} ∅
{1, 2, 3, 5} {1, 2, 3, 4, 5} {1, 3, 5}
← {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 3, 5}
{1, 3, 5} {1, 2, 3, 4, 5} {1, 3, 5}

Ejercicio 5 (11/2 puntos)

Dados un alfabeto Σ, un lenguaje L ⊆ Σ y una palabra u ∈ Σ , determine si en todo
∗ ∗

caso la siguiente igualdad es cierta:

{u}(u−1L) = L.

Solución:
La igualdad es falsa. Como prueba, considérese el alfabeto Σ = {a, b}, el lenguaje
L = {a} y la palabra u = b.
Puede verse que:
u−1L = b−1 {a} = ∅,
por lo que:
{u}u−1L = {u}∅ = ∅,

que no es igual a L.
ETSINF TAL Examen Final 02/02/2023

Segundo Parcial
(Justifique formalmente las respuestas o proporcione resultados parciales)

Ejercicio 1 (2 puntos)
Determine si el siguiente lenguaje es regular o no:

L = {ai bj ck : j = i + k ∧ i 6= k}

Solución:
El lenguaje no es regular. Demostraremos que no lo es por reducción al absurdo.
Supongamos que L es regular, por lo tanto, existirá un AFD A = (Q, Σ, δ, q0 , F ) tal
que L(A) = L.
Consideremos el conjunto infinito de palabras C = {ai : i > 1}, y tomemos dos
palabras cualesquiera de este conjunto, u = an y v = am con n 6= m.
Considerando la palabra w = bn , comprobamos que uw = an bn ∈ L, pero también
que vw = am bn 6∈ L. La consecuencia de esto es que el procesamiento en A de las
palabras u y v alcanzan estados distintos (δ(q0 , u) 6= δ(q0 , v)).
El conjuunto C contiene infinitas palabras y la elección de u y v se hace sin condición
de ningún tipo. Y por lo anterior, cada una de las palabras en C deberı́a alcanzar un
estado distinto al alcanzado por el análisis de cualquier otra palabra en C. Con esto,
el AFD A deberı́a tener infinitos estados, lo que supone una contradicción, e implica
que el lenguaje no es regular.
De forma análoga, puede verse que, independientemente de las palabras uy v escogidas
los cocientes u−1 L y v −1 L son distintos, por lo que la relación ≡L es de ı́ndice infinito
y por lo tanto L no es regular.

Ejercicio 2 (1 punto)
Proporcione una expresión regular para el lenguaje:

L = {an bm : n mód 2 6= m mód 2}.

Solución:
Una expresión válida es (aa)∗ (a+b)(bb)∗ . Otra posible respuesta válida es (aa)∗ (bb)∗ b+
(aa)∗ a(bb)∗ .

Ejercicio 3 (1 punto)
Enumere las primeras 8 palabras en orden canónico del lenguaje descrito por la expresión
regular (a + bb)∗ + ba∗ a.

Solución:
λ, a, aa, ba, bb, aaa, abb, baa
ETSINF TAL Examen Final 02/02/2023

Ejercicio 4 (2 puntos)
Utilice el método visto en clase para analizar el siguiente autómata y obtener una expre-
sión regular que describa el lenguaje aceptado por él.
a b

b b
q1 q2 q3
a a

Solución:
Eliminamos el estado sumidero ya que no afecta al lenguaje aceptado por el autóma-
ta. El sistema de ecuaciones en expresiones regulares asociado al autómata es:

X1 = aX1 + bX2

X2 = aX1 + bX3

X3 = aX2 + bX3 + λ


Aplicando el Lema de Arden en la ecuación para X3 tenemos:

X3 = b∗ (aX2 + λ) = b∗ aX2 + b∗

sustituyendo en el sistema el valor de X3 obtenemos:

(
X1 = aX1 + bX2
X2 = aX1 + bb∗ aX2 + bb∗

Aplicando el Lema de Arden spara X2 se obtiene que:

X2 = (bb∗ a)∗ (aX1 + bb∗ ) = (bb∗ a)∗ aX1 + (bb∗ a)∗ bb∗ ,

sustituyendo una vez más:

X1 = aX1 + b(bb∗ a)∗ aX1 + b(bb∗ a)∗ bb∗ = (a + b(bb∗ a)∗ a)X1 + b(bb∗ a)∗ bb∗ ,

y aplicando finalmente el Lema de Arden se obtiene la expresión buscada:

X1 = (a + b(bb∗ a)∗ a)∗ b(bb∗ a)∗ bb∗ .

Ejercicio 5 (2 puntos)
Dados el siguiente autómata y homomorfismo:
a b
(
b b h(a) = ba
q1 q2 q3
h(b) = ab
a a
obtenga un AFD que acepte el lenguaje h−1 (L(A)) − (ab)−1 L(A).
ETSINF TAL Examen Final 02/02/2023

Solución:
Obtenemos primero un autómata para h−1 (L(A)).
a a, b b

b
A B a C
donde el estado C no es accesible y puede eliminarse.
Obtenemos ahora un autómata para el lenguaje (ab)−1 L(A).

b
2 3 b
a
b a

1 a

Para realizar la diferencia es necesario primero complementar el automáta (completo)

que acepta el lenguaje (ab)−1 L(A):

b
2 3 b
a
b a

1 a

y realizar ahora la interesección entre los autómatas para el homomorfismo y el co-

ciente:

a a
A2 A1

b b
a a
b B3 B2 B1 a
b b

Ejercicio 6 (2 puntos)
Dado el alfabeto Σ = {a, b} y un lenguaje L ⊆ Σ∗ , se define la operación P (L) como la
que borra el primer sı́mbolo de las palabras de L que tienen los dos primeros sı́mbolos
iguales y no modifica el resto de palabras.
¿Es P (L) cerrada en la clase de los lenguajes regulares?
ETSINF TAL Examen Final 02/02/2023

Solución:
La operación es de cierre en la clase de los lenguajes regulares. En efecto, conside-
ramos primero los siguientes lenguajes regulares (pueden describirse con expresiones
regulares):

Laa = aa(a + b)∗

Lbb = bb(a + b)∗

Con lo que pueden obtenerse el resultado de la operación sobre las palabras con los
dos primeros sı́mbolos iguales como:

a−1 (L ∩ Laa ) ∪ b−1 (L ∩ Lbb ),

y pueden seleccionarse las palabras sobre las que no hay que aplicar operación alguna
como:

L ∩ (Laa ∪ Lbb ),
con lo que, combinando ambos resultados, la operación P (L)puede describirse como:

P (L1 , L2 ) = a−1 (L ∩ Laa ) ∪ b−1 (L ∩ Lbb ) ∪ (L ∩ (Laa ∪ Lbb )).

Como la operación puede definirse como composición, sobre lenguajes regulares, de

operaciones de cierre para la clase de lenguajes regulares, puede concluirse que la
operación P es cerrada en la clase de los lenguajes regulares.
ETSINF TAL Examen Final 02/02/2023

Evaluación del laboratorio

Ejercicio 1
Un autómata finito deteminista cumple la propiedad P si:

1. El estado inicial no recibe transición alguna.

2. Dado cualquier sı́mbolo a del alfabeto, todas las transiciones en el autómata etique-
tadas con ese sı́mbolo alcanzan el mismo estado.

Diseñe un módulo Mathematica que, dado un AFD A accesible, devuelva True si el

autómata cumple la propiedad P y devuelva False caso contrario.

Solución:

Local[A_] := Module[{QQ, est, s, l},

QQ = {};

If[Cases[A[[3]], {_,_, A[[4]]}]=!={},Return[False]];

For[s = 1, s <= Length[A[[2]]], s++,

l = Cases[A[[3]], {_, A[[2, s]], _}];
est = {};
For[i = 1, i <= Length[l], i++,
est = Union[est, {l[[i, 3]]}];
]; (* est: estados alcanzados por el sı́mbolo s *)
If[Length[est] > 1, Return[False]];
]; (* for *)

Return[True]
]
ETSINF TAL Examen Final 02/02/2023

Funciones Mathematica útiles

Length[l1]: Devuelve la longitud de la lista.

Join [l1, l2]: Concatena dos listas.

Union[l1, l2]: Devuelve una lista con los elementos que se encuentran en l1 o l2 y los
ordena.

Intersection[l1, l2]: Devuelve una lista con los elementos comunes a l1 y l2.

Complement[l1, l2]: Devuelve una lista con los elementos de l1 que no estan en l2.

Sort[l1]: Devuelve l1 ordenada de menor a mayor (no actualiza l1).

Reverse[l1]: Devuelve el reverso de l1.

RotateRight[l1]: Devuelve l1 con los elementos desplazados un lugar a la derecha (el último
pasa a ser el primero).

RotateLeft[l1]: Idéntico al anterior pero desplazando hacia la izquierda.

First[l1]: Devuelve el primer elemento de la lista.

Rest[l1]: Lista l1 sin el primer elemento.

EvenQ[n]: Devuelve si el número n es par.

OddQ[n]: Devuelve si el número n es impar.

Mod[n,m]: Devuelve el resultado de n módulo m .

Drop[l1, n]: Devuelve la lista sin los primeros n elementos.

Take[l1, n]: Devuelve los primeros n elementos de la lista.

Take[l1, -n]: Devuelve los últimos n elementos de la lista.

Take[l1, {n,m}]: Devuelve los elementos de la lista desde la posición n a la m.

Append[l1, x]: Añade el elemento x al final de la lista.

Prepend[l1, x]: Añade el elemento x al comienzo de la lista.

AppendTo[l1, x], PrependTo[l1, x]: Idénticas a las anteriores pero actualizan la lista.

Position[l1,x]: Devuelve una lista con las posiciones de x en l1.

MemberQ[l1,x]: Devuelve True si x pertenece a l1 y False si no.

Cases[lista, patrón]: Devuelve una lista con los elementos de lista que concuerdan con
patrón. El patrón puede contener el sı́mbolo (subrayado), que se sustituye por cualquier
sı́mbolo.