exams

Examen Parcial de Aut´
omatas y Lenguajes Formales
12 de diciembre de 2003
Resolver los siguientes problemas. Tiempo 2 horas.
1. Dar una gram´atica y demostrar que es correcta para
L = {am bn | 2m < n < 3m}.
2. Dar un aut´omata de pila determinista y demostrar que es correcto para el
lenguaje formado por las palabras de a+ b+ a+ b+ con el mismo n´
umero de aes
que de bes. (Basta con definir L(q,γ) para todas las posibles configuraciones
y demostrar una de ellas que no sea la m´as simple).

Examen de Aut´
omatas y Lenguajes Formales
14 de febrero de 2003
Resolver 4 de los siguientes problemas. Tiempo 3 horas.
1. Sean M1 y M2 dos AFD con funciones de transici´on δ1 y δ2 , respectivamente.
Demostrar que si δ es la funci´on de transici´on definida sobre el producto de
estados:
δ((p, q), a) =(δ1 (p, a), δ2 (q, a))
entonces para toda palabra w
˜
δ((p,
q), w) = (δ˜1 (p, w), δ˜2 (q, w)).
2. ¿Es el lenguaje
{wαw t | w, α ∈ {a, b}+ }
regular? (Nota: ejercicio m´as apropiado para el plan viejo)
3. Describir el lenguaje generado por la gram´atica
S → aSb | aaSb | λ
en t´erminos de una relaci´on entre el n´
umero de a’es y b’es y demostrar la
respuesta.
4. Sea
L = {ai bj ck | i = j + k, j ≥1, k ≥ 1}.
Dar un aut´omata de pila para L#, describir los lenguajes asociados a las
configuraciones y demostrar uno de ellos.

5. Sea L semidecidible. ¿Es
L = {w n | n ≥ 0 ∧ w ∈ L}
semidecidible? Demostrar la respuesta.
Examen d’aut`
omats i llenguatges formals
Primera part. 17 de febrer de 2005
Resoleu els problemes. Temps 2 hores.
1. Donau un aut`omat finit per el conjunt de les paraules sobre{a, b} tals que tot
abb apareix immediatament despr´es de bba, i demostrau-ne la correcci´o.
2. Suposem que recL(x) ´es un programa determinista que fa L un llenguatge
semidecidible. Escriviu en detall un programa que reconegui
L = {w | w ∈ L2 ∨ w ∈ L3 }.

Examen d’aut`
omats i llenguatges formals
Segona part. 17 de febrer de 2005
Resoleu els problemes. Temps 2 hores.
3. Sigui G = (V, Σ, S, P )una gram`atica tal que totes les produccions s´on de la
forma A → αB, amb α ∈ Σ∗ i B ∈ V . Per a cada variable X es defineix el
llenguatge
∗
LX = {w ∈ Σ∗ | S ⇒ wX}.
Sigui ara A una variable de G tal que les u
´ niques produccions a la part dreta
de les quals apareix s´on
B → α1 A, C → α2 A, D → α3 A.
Demostrau aleshores que
L A = L B α1 + L C α2 + L D α3 .
(ajuda: s´on dues direccions, no ´es perinducci´o, i nom´es cal fer servir les
definicions donades).
4. Donau un aut`omat amb pila determinista per a
L = {a2i bj ck | 2i = j + k}.
Per a cada bucle, escriviu la seva invariant. Verifiqueu la primera instrucci´o
del primer bucle, introduint una postcondici´o correcta.

Examen Parcial de Aut´
omatas y Lenguajes Formales
5 de noviembre de 2002
Resolver los siguientes problemas. Tiempo 2horas.
1. Completar la siguiente frase y demostrarla: el siguiente aut´omata reconoce las
palabras en {a, b} tales que toda subpalabra de longitud cuatro ...

b

b

b

a
a

A

b

D

a

b

a
a

B
b

F

b
E
a

C

b

b

a, b
G

2. Considerar la ecuaci´on de lenguajes X = X c 1 en el alfabeto Σ = {0, 1}.
Demostrar que tiene soluci´on u
´ nica (ayuda: suponer que hay dos soluciones
X e Y , y demostrar queson iguales por inducci´on).
Examen Parcial de Aut´
omatas y Lenguajes Formales
8 de noviembre de 2005
Resolver los siguientes problemas. Tiempo 2 horas.
1. Dar un aut´omata de estados finitos para el lenguaje de las palabras tales que
el n´
umero de 1s menos el n´
umero de 0s es m´
ultiplo de 4 y verificar que es
correcto.
2. Sea Σ = {[, ], 1}. Demostrar que
L = {[n 1]n | n ≥ 0}
no es regular.

3Examen de Aut´
omatas y Lenguajes Formales
Primera parte. 3 de septiembre de 2004
Resolver los problemas. Tiempo 2 horas.
1. Completar la frase y demostrarla: el aut´omata siguiente reconoce las palabras
tales que el n´
umero de 1s ....

0
1

1
0

0
0

1

2
1

2. Dar una gram´atica para el lenguaje de las palabras tales que su n´
umero de
aes es igual a uno m´as que el n´
umero de bes....