Modelo de examen: Nacional-UE-Guinea Original, Tipo:
Cada acierto suma un punto sobre 10; cada error descuenta 0.3 puntos. Las preguntas no respondidas no pun-
tian. NO SE PERMITE NINGUN TIPO DE MATERIAL
1. Dada la siguiente gramatica GG = ({5, A, B}, {x, y}, S, P), donde S es el simbolo inicial de la gramatica y
P el siguiente conjunto de producciones:
S — xvAy
S—> «Byy
A— xvAy
A-y
B- xByy
Boy
Indicar cual de las siguientes afirmaciones es verdadera:
(a) L(G) es un lenguaje regular.
(b) Ges una gramatica regular.
(c) L(G) = {a"y"TM*1:n > 0} U {a"y?"t1 in > 0}
(d) Ninguna de las anteriores afirmaciones es verdadera.
2. Indique cual de las siguientes afirmaciones es verdadera:
(a) Encada transicién, una maquina de Turing tnicamente puede leer un simbolo de la cinta de entrada y no
puede escribir ni mover la cabeza de lectura/escritura por la cinta.
(b) En cada transicién, una maquina de Turing inicamente puede leer un simbolo de la cinta de entrada y
escribir un simbolo en la cinta de entrada, pero no puede desplazar la cabeza de lectura/escritura en la
cinta.
(c) Encada transici6n, una maquina de Turing puede leer y escribir un simbolo en la cinta de entrada. Ademas,
en cada transici6n, desplaza la cabeza de lectura/escritura un lugar a la izquierda o un lugar a la derecha
por la cinta.
(d) Ninguna de las anteriores afirmaciones es verdadera.
3. Dado el alfabeto & = {a, b, c}, sea M el autémata definido de la siguiente manera:
M= ({p, qT, s}, {a, b, c}, 6, P, {q, r})
donde 6 se define mediante el siguiente diagrama de transiciones:
Indicar cual de las siguientes afirmaciones es verdadera:
(a) L(M) contiene a la cadena vacia.
(b) L(M) se puede expresar mediante la expresidn regular (b + a)*b + b*e
(c) L(M) se puede expresar mediante la expresién regular b(b + a)* + cb*
(d) Ninguna de las anteriores afirmaciones es verdadera.
4. Dado el alfabeto © = {a, b}, sea LE el lenguaje formado por los palindromos de longitud impar (recuerde que
un palindromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda). Considere el
autémata a pila M/ definido de la siguiente manera:
M = ({p, q,?s s}, u,T, 6, p, Zo, {s})
donde T = {Zp, a, b} es el conjunto de simbolos de pila y 6 se define mediante el siguiente diagrama de
transiciones (la pila se encuentra inicialmente vacia):
Indicar para qué valores de las etiquetas: etiqueta-1, etiqueta-2 y etiqueta-3 se cumple que L = L(M):
(a) etiqueta-1=b, €; b, etiqueta-2=a, €; €, etiqueta-3=b, b; €
(b) — etiqueta-1=b, b; €, etiqueta-2=a, €; a, etiqueta-3=b, b; €
(c) etiqueta-1=b, b; €, etiqueta-2=a, €; €, etiqueta-3=b, b; €
(d) etiqueta-1=b, b; €, etiqueta-2=a, €; a, etiqueta-3=b, e€; €
5. Dado el alfabeto & = {0,1}, sea Ly el lenguaje que representa la expresi6on regular:
11(0 + 1)*
Sea Ly el lenguaje que genera la gramatica definida de la siguiente manera:
G = ({S,A, B, F}, %, S, P)
donde S es el simbolo inicial de la gramatica y P es el siguiente conjunto de producciones:
S—>0A
S—1B
A— 1B\0OF
B-O0A\1F
F > OF |\1F |e
Indicar cual de las siguientes afirmaciones es verdadera:
(a) Ly, = Ly
(b) £1 C Ly
(c) Lech
(d) Ninguna de las anteriores afirmaciones es verdadera.
6. Dado el alfabeto & = {ax, y, z}, sea L el lenguaje definido de la siguiente manera:
L= {aTM(axy)"(yz)"a2TM :n > 0,m > 0}
y sea G la gramatica definida de la siguiente manera:
G = ({S,
A, B}, ©, S, P)
donde S es el simbolo inicial de la gramatica y P es el siguiente conjunto de producciones:
S—- 2Az
A— £Azx
A—->B
B- zyByz
B- xryyz
Indicar cual de las siguientes afirmaciones es verdadera:
(a) L=L(G)
(b) LCL(G)
(c) L(G) CL
(d) Ninguna de las anteriores afirmaciones es verdadera.
7. Dado el alfabeto & = {a, b, c}, sea LE el lenguaje aceptado por el aut6mata M definido de la siguiente manera:
M = ({p, 4,7, 8}, 4,6, p, {p, r})
donde la funcién de transicién 6 se define mediante el siguiente diagrama de transiciones:
Indicar cual de las siguientes afirmaciones es verdadera:
(a) MM es un autémata finito determinista.
(b) L se puede representar mediante la expresion regular c*(aa)* + ba*
(c) Todas las cadenas contenidas en L tienen un numero par de simbolos a
(d) Ninguna de las anteriores afirmaciones es verdadera.
8. Dado el alfabeto & = {a, b}, sea L el lenguaje que acepta el aut6mata M definido de la siguiente manera:
M= ({p, qs1Ts s}, x, 6, p, {q, r})
donde 6 se define mediante el siguiente diagrama de transiciones:
b
Indicar cual de las siguientes afirmaciones es verdadera:
(a) L se puede expresar mediante la expresion regular (a + b)
(b) LZ se puede expresar mediante la expresién regular (a* + b*)
(c) LD se puede expresar mediante la expresién regular (a + b)(a + b)*
(d) Ninguna de las anteriores afirmaciones es verdadera.
9. Dado el alfabeto & = {a, b}, sea L el lenguaje definido de la siguiente manera:
L = {aa"bb"*! :n > 0}
Indicar cual de las siguientes afirmaciones es verdadera:
(a) Les un lenguaje regular.
(b) Les un lenguaje independiente del contexto no regular.
(c) Les un lenguaje recursivamente enumerable no independiente del contexto.
(d) Ninguna de las anteriores afirmaciones es verdadera.
10. Dado el alfabeto & = {0,1}, sea M la Maquina de Turing definida de la siguiente manera:
M = ({40; 71; ar} x, {0, 1, B}, 6, 90, B, {az})
donde la funcién de transicién 6 se define mediante el siguiente diagrama de transiciones:
Indicar cual de las siguientes afirmaciones es verdadera:
(a) L(M) es regular y puede expresarse mediante la expresi6n regular 0*1*
(b) L(M) es regular y puede expresarse mediante la expresién regular 0*11*
(c) L(M) es independiente del contexto no regular.
(d) Ninguna de las anteriores afirmaciones es verdadera.
