TEORA DE AUTMATAS I

Informtica de Sistemas

Soluciones a las cuestiones de examen del curso 2007/08

Febrero 08, 1 semana

1. Indique cul de las afirmaciones siguientes es FALSA: a) Un autmata finito determinista utilizado como reconocedor de lenguajes con al menos una cadena necesariamente tiene que tener al menos un estado de aceptacin

b) Dada una gramtica regular G, siempre existe un autmata finito M tal que L(G) = L(M) y M tiene un nico estado de aceptacin

c) Un autmata reconoce una cadena cuando alcanza un estado de aceptacin durante su lectura

Solucin: C. Para que una cadena sea aceptada por autmata finito o de pila es necesario que la lectura del ltimo smbolo de la cadena le conduzca a un estado de aceptacin. A es trivialmente verdadera. B es verdadera: dado un autmata finito, siempre es posible convertirlo en otro que tenga un nico estado de aceptacin y que acepte el mismo lenguaje (vase el problema 26 del libro de texto).

2. Indique cul de los siguientes lenguajes NO es regular:

a) L ={anbm n+m > 5, n > 0, m 0} b) L ={anbm m > 5n, n > 0} c) L ={an n/10 es un entero} Solucin: B. En el caso de los lenguajes A y C los lenguajes pueden representarse

mediante las expresiones regulares {aaaaaaa*b* aaaaaa*bb* aaaaa*bbb* aaaa*bbbb* aaa*bbbbb* aa*bbbbbbb*} y {aaaaaaaaaa}*, respectivamente. La demostracin de que el lenguaje B no es regular es anloga a demostracin de que no lo es el lenguaje {anbn}.

3. Sean L1 y L2 los lenguajes aceptados, respectivamente, por los autmatas de las figuras 1) y 2). Indique cul de las siguientes afirmaciones es cierta:

a) L1 = L2, uno de los dos autmatas es determinista y el otro no lo es.

b) L1 = L2, si consideramos que uno de los diagramas est incompleto.

c) L1 L2

a

a

b

a

b

b b

b

a

b

a

a

b b

Fig . 1 F ig. 2

b

2

Solucin: C. El autmata de la figura 2 no acepta la cadena abb, mientras que el de la figura 1) s la acepta.

4. Indique cul de las siguientes gramticas genera el lenguaje L = {amb2mc2n m >0, n 0}

a) S AB, A aAb | ab, B bBc | b) S AB, A aAbb | abb, B cBc | c) Las dos gramticas anteriores generan el lenguaje L

Solucin: B. La gramtica del apartado A genera el lenguaje L = {anbmcp m = n+p, n > 0, p 0}. A la vista de las reglas de la gramtica B es evidente que genera el lenguaje indicado (por cada a se generan dos bs; el nmero de cs es arbitrario pero necesariamente par).

5. Considere el lenguaje 2-menos(L) = {w | vw L y |v| = 2}, v, w *, = {a,b}. Indique cul de las siguientes afirmaciones es FALSA. a) Si L es un lenguaje regular entonces 2-menos(L) es regular

b) Aunque L sea regular, es posible que 2-menos(L) no sea regular

c) Aunque L no sea regular 2-menos(L) puede ser regular

Solucin: B. A es verdadera: el autmata finito que reconoce 2-menos(L) puede construirse fcilmente a partir del autmata que reconoce a L sin ms que aadir un nuevo estado de inicio con arcos etiquetados por hacia todos los estados alcanzables mediante un camino de longitud 2 desde el estado inicial del autmata de partida. De ah se deduce que B es falsa. C es verdadera: considere L el lenguaje cuyos dos primeros smbolos indican si la longitud total de la cadena es un nmero primo (p.e. aa indica que la longitud de la cadena es un nmero primo y bb que no es un nmero primo); en este caso: 2-menos(L) = *, lenguaje regular.

6. Indique cul de las siguientes afirmaciones, referidas a la estrella de Kleene de un conjunto, es FALSA:

a) La estrella de Kleene de un alfabeto , *, es el lenguaje de todas las cadenas que se pueden formar con smbolos de , incluyendo la cadena vaca. b) x * significa que x es una cadena formada con smbolos de , o bien la cadena vaca

c) La estrella de Kleene de un conjunto siempre es un conjunto infinito

Solucin: C. A y B son ciertas por definicin. C es falsa, ya que si el conjunto es el conjunto vaco o el conjunto {}, la estrella de Kleene es {}.

3

7. Sean L1, L2 y L3 los lenguajes reconocidos, respectivamente, por los autmatas de las figuras 1), 2) y 3). Indique cul de las siguientes afirmaciones es verdadera.

a

a

b

b

F ig . 1

F ig . 2 a

a

b

b

Fig. 3

a) L3 = L1 L2 b) L3 = L1 L2 c) L3 L1 L2 Solucin: C. El autmata de la figura 3 no reconoce al lenguaje concatenacin, que s

reconoce el autmata:

a

a

b

b

abba L3, abba L1 L2, abba L1 L2 8. Indique cul de las siguientes afirmaciones sobre el lema de bombeo para lenguajes regulares es verdadera:

a) No lo cumple el lenguaje de palndronos de longitud par, pero lo cumple el lenguaje de palndronos de longitud impar

b) Se refiere a lenguajes infinitos; de hecho, todo lenguaje finito lo cumple de forma trivial

c) Puede utilizarse para demostrar que un lenguaje es regular, pero no para demostrar que un lenguaje no es regular.

Solucin: B. Se cumple de forma trivial en el caso de los lenguajes finitos: dado que siempre puede encontrarse una constante k mayor que cualquier cadena del lenguaje, claramente ser cierto que para toda cadena de la forma xyz L con |y| k, " ya que no hay cadenas en L tal que |y| k. El lema de bombeo puede utilizarse para demostrar que un lenguaje no es regular, pero no para demostrar que un lenguaje es regular, ya que existen lenguajes que verifican el lema de bombeo y, sin embargo, no son regulares.

9. Sea un lenguaje L que puede expresarse como concatenacin de dos lenguajes L1 y L2. Sean G1(S1,T1,V1,R1) y G2(S2,T2,V,R2), T1 T2 = ,

(Vi : conjunto finito de smbolos bsicos (terminales) Ti : " " " " que nombran construcciones del lenguaje (no terminales) Si : smbolo de inicio (T) Ri : conjunto finito de reglas de reescritura)

entonces

4

a) G( S,T,V,R) donde R = R1 R2 S S1S2 es siempre una gramtica para L b) G( S,T,V,R) donde R = R1 R2 S S1S2 S es siempre una gramtica para L c) La gramtica G no puede deducirse a partir de las gramticas G1 y G2

Solucin A. Es trivial demostrar que las cadenas derivadas de la gramtica G consistirn en todas las posibles concatenaciones de cadenas derivadas de la gramtica G1 con cadenas derivadas de la gramtica G2. As, p.e., L = {anbncmdm}. Gramticas para {anbn} y {cmdm} son S1 aS1b | y S2 cS2d | respectivamente. Combinando estas dos gramticas obtenemos una gramtica para L: S S1S2 S1 aS1b | S2 cS2d | .

10. Indique cul de las siguientes afirmaciones es FALSA: a) Los lenguajes regulares podran ser aceptados por mquinas de Turing que siempre moviesen su cabeza a la izquierda.

b) En realidad una mquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autmata finito principalmente en el mecanismo de aceptacin de cadenas: una mquina de Turing entra en un estado de aceptacin en cuanto concluye sus clculos

c) Una mquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autmata finito principalmente en que tiene poder de escribir en su cinta, y por tanto almacenar datos a modo de un autmata de pila y reconocer lenguajes independientes del contexto.

Solucin:C. Una mquina de Turing que siempre moviese su cabeza hacia la izquierda podra utilizarse para realizar las funciones de un autmata finito: la cadena se registrara invertida en la cinta y la cabeza de lectura de la mquina se situara inicialmente a la derecha del primer smbolo. Al moverse la cabeza slo hacia la izquierda, aunque la mquina pudiera escribir smbolos en su cinta nunca podra leer estos smbolos, y por tanto es como si no tuviera capacidad para almacenarlos y no podra operar como un autmata de pila.

11. Sea L un lenguaje regular y L = {x | x L y la longitud de x es un nmero par}. Es L regular?

a) L es regular cualquiera que sea L.

b) L nunca es regular.

c) Depende de L.

Solucin:A. Siempre podra expresarse como interseccin de dos lenguajes regulares: el lenguaje L y el lenguaje de las cadenas de longitud par del alfabeto considerado.

5

12. La concatenacin de dos lenguajes de es un subconjunto de a) b) c)

Solucin: A. La concatenacin de dos lenguajes es el lenguaje que resulta al concatenar las respectivas cadenas (la concatenacin de dos cadenas es una nueva cadena) y por tanto pertenece a . es el conjunto de pares ordenados formados por dos smbolos de , y es el conjunto de pares ordenados formados por dos cadenas de

ByC

Bzx

B

.

13. El lenguaje generado por la siguiente gramtica es

S xAA xBA yB yBC xC xyz

a) regular.

b) independiente del contexto (en sentido estricto).

c) estructurado por frases (en sentido estricto).

Solucin: A. El lenguaje contiene exactamente 8 cadenas. Observe que no se pregunta por el tipo de gramtica (que es independiente de contexto), sino por el tipo de lenguaje (que, adems de ser independiente de contexto, es regular).

14. Indicar si la expresin regular (x y)(x y)* representa el mismo lenguaje que acepta el siguiente autmata.

x x

y y

a) Verdadero

b) Falso

c) Depende del alfabeto

Solucin: A. En ambos casos se trata del lenguaje formado por las cadenas que contienen un solo smbolo.

6

15. Sea L un lenguaje generado por una gramtica libre de contexto en forma normal de Chomsky. Existe otra gramtica en forma normal de Chomsky que genere el complemento de L?

a) S, para todo G.

b) No, nunca.

c) Depende de G. Solucin: B. El complemento de L contiene la cadena vaca.

16. Los palndromos (palabras capicas) del idioma castellano, tales como a, y, dad, oso, erre, etc., constituyen un

a) lenguaje regular.

b) lenguaje independiente del contexto (en sentido estricto).

c) lenguaje estructurado por frases (en sentido estricto). Solucin: A. Es un lenguaje finito, y por tanto, regular.

Febrero 08, 2 semana

17. Indique cul de los siguientes lenguajes es independiente del contexto:

a) L = { anbmc2nd2n n > 0, m > 0} b) L = { (ab)ncndm n > 0, m > 0, n m} c) L = { a2nbmcn n > 0, m 0, n es par y m es impar} Solucin: C. Es fcil disear un autmata de pila que acepte el lenguaje. En cuanto a

los lenguajes A y B, una nica pila no permite el recuento independiente de 3 exponentes.

18. Un hombre que viaja con un lobo, una cabra y un repollo desea cruzar un ro. Dispone de una barca donde slo caben l y una de sus posesiones a la vez. Si dejara solos al lobo y la cabra el lobo comera a la cabra, y si dejara solos a la cabra y al repollo la cabra comera el repollo. Muestra el siguiente autmata todas las secuencias posibles de cruces del ro mediante las cuales el hombre consigue pasar a la otra orilla con todas sus pertenencias? (l: el hombre cruza con el lobo; c: el hombre cruza con la cabra; r: el hombre cruza con el repollo; s: el hombre cruza slo; l: el hombre regresa a la orilla de partida con el lobo; c: el hombre regresa a la orilla de partida con la cabra; r: el hombre regresa a la orilla de partida con el repollo; s: el hombre regresa a la orilla de partida slo.).

a) S las muestra, pero el diagrama est incompleto

b) S las muestra, y el diagrama est completo

c) No las muestra

Solucin: A. Para que estuviera completo habra de aadirse un estado de captacin global.

7

c

c s

s

c c

s

s

c c c c

l l

rr

r r

ll

19. Considere el autmata M = (Q, , , q0, F), donde Q = {q0,q1} es el conjunto de estados del autmata, = {a,b} es el alfabeto, F = {q1} es el conjunto de estados de aceptacin y (q0,a) = q1, (q0,b) = q0, (q1,a) = q1, (q1,b) = q0 es la funcin de transicin.

Indique cul de las siguientes afirmaciones es cierta: a) M es no determinista

b) M reconoce el lenguaje L = {wa | w {a,b}*} c) La funcin no define un autmata finito correcto Solucin: B. El autmata descrito es sencillo:

q 0 q 1

b

a

a

b

20. Sean L1 = {0x | x {0,1}*} y L2 = {x0 | x {0,1}*}. Sea L el lenguaje reconocido por el autmata de la figura. Considere el alfabeto = {0,1}.

0

1

1

0 0

1 0

1

0

1

8

a) L = L1 L2 b) L = L1 L2 c) L es el lenguaje complementario de L1 en * Solucin A. El autmata reconoce el lenguaje de las cadenas que empiezan y terminan

por cero.

21. Indique cul de las siguientes afirmaciones, relativas a la estrella de Kleene de un lenguaje L es verdadera:

a) El conjunto de cadenas que pueden formarse concatenando cualquier nmero de cadenas cada una de las cuales pertenece a L {}. b) L* = {wn | n 0 y w L} c) Para todo L que contenga al menos una cadena L* es infinito

Solucin: A. C es falso ya que si L = {} L* = {}. 22. Considere la siguiente gramtica e indique cul de las siguientes afirmaciones es FALSA:

S PVP, A al, P AN, A el, V ama, N perro, V odia, N gato, N ratn (cada palabra en minsculas se considera un smbolo del alfabeto) a) Todas las frases generadas mediante la gramtica son frases gramaticalmente correctas en castellano

b) Muchas de las frases generadas no son gramaticalmente correctas en castellano

c) El castellano no puede generarse mediante una gramtica estructurada por frases de reglas sencillas como si de un lenguaje formal se tratase

Solucin A. La gramtica genera frases como: el perro/gato/ratn odia el perro/gato/ratn y al perro/gato/ratn odia al perro/gato/ratn, gramaticalmente incorrectas. Slo los lenguajes formales se generan mediante gramticas estructuradas por frases de reglas sencillas.

23. Sea un lenguaje L que puede expresarse como unin de dos lenguajes L1 y L2. Sean G1(S1,T1,V1,R1) y G2(S2,T2,V,R2), T1 T2 = ,

(Vi : conjunto finito de smbolos bsicos (terminales) Ti : " " " " que nombran construcciones del lenguaje (no terminales) Si : smbolo de inicio (T) Ri : conjunto finito de reglas de reescritura)

entonces a) G( S,T,V,R) donde R = R1 R2 S S1 | S2 es siempre una gramtica para L b) G( S,T,V,R) donde R = R1 R2 S S1 | S2 S es siempre una gramtica para L

c) La gramtica G no puede deducirse de las gramticas G1 y G2

9

Solucin: A. Es trivial demostrar que las cadenas derivadas de la gramtica G consistirn en todas las cadenas derivadas de la gramtica G1 ms todas las cadenas derivadas de la gramtica G2. As, p.e., L = {z {a,b}* | z = xxR para algn x, o |z| is impar}. Gramticas para L1 = {xxR | x {a,b}*} y L2 = {z {a,b}* | |z | es impar} son

S1 aS1a | bS1b | y S2 XXS2 | XX a | b respectivamente. Combinando estas dos gramticas obtenemos una gramtica para L:

S S1 | S2S1 aS1a | bS1b | S2 XXS2 | XX a | b 24. Indique cul de las siguientes afirmaciones es verdadera:

a) Un autmata finito nunca puede meterse en un ciclo que se ejecute indefinidamente

b) Un autmata de pila determinista nunca puede meterse en un ciclo que se ejecute indefinidamente

c) Una mquina de Turing determinista puede meterse en un ciclo que se ejecute indefinidamente.

Solucin:C. Si un autmata tiene transiciones lambda puede meterse en ciclos que se ejecuten indefinidamente sin leer ningn smbolo de la cadena de entrada. Es trivial ver que las mquinas de Turing pueden entrar en ciclos de ejecucin infinitos.

25. Indique cul de las siguientes afirmaciones es verdadera:

a) Con una nica mquina de Turing pueden reconocerse tres lenguajes: el lenguaje de las cadenas que acepta, el lenguaje de las cadenas que rechaza y el lenguaje de las cadenas que llevan a la mquina a un bucle de ejecucin infinita.

b) Es posible disear una mquina de Turing de tres cintas que reconozca tres lenguajes.

c) Con una nica mquina de Turing, ya sea de una o varias cintas, determinista o no determinista, slo es posible reconocer un lenguaje

Solucin: B. En realidad, con una nica mquina de Turing, ya sea de una o varias cintas, determinista o no determinista, es posible reconocer un nmero indefinido de lenguajes (imagine, p.e., una mquina formada componiendo varias mquinas de Turing Mi que reconocen respectivos lenguajes Li mediante mensajes de aceptacin que identifican al lenguaje). Las cadenas que llevan a la mquina a un bucle de ejecucin infinita no pueden ser reconocidas, ya que es imposible determinar si la ejecucin va a terminar o no en algn momento (es el problema de los lenguajes no decidibles).

10

26. Indique cul de las siguientes afirmaciones, referidas a la mquina de Turing de la figura es FALSA:

a; ,R

b;b,R

a;a,R

;a ,L b;b,L

a;a ,L

; ,R b;a,R

; ,R

a;a,L

; ,L a;b,R b;a, R

a;b ,R b;b,L

a) La mquina implementa la funcin f(anbm) = ambn, n>0, m>0.

b) Si la mquina se arranca con la cabeza de lectura apuntando al primer smbolo empezando por la izquierda de aabbbb la mquina se detiene con la cabeza de lectura apuntando al primer smbolo empezando por la izquierda de aaaabb.

c) La mquina llega a un estado de parada sea cual sea la configuracin inicial de cinta.

Solucin: C. Si la mquina se arranca, p.e., con una configuracin de cinta ba..., la mquina termina anormalmente.

27. El lenguaje xmynzp, donde m, n y p son enteros no negativos tales que m+n=p, es...

a) regular.

b) independiente del contexto (en sentido estricto).

c) estructurado por frases (en sentido estricto).

Solucin: B. Es fcil construir el correspondiente autmata.

28. Un lenguaje generado por una gramtica independiente de contexto

a) es siempre regular

b) nunca es regular

c) depende de los casos Solucin: C. Una gramtica independiente del contexto puede generar lenguajes independientes del contexto regulares o no regulares. Es fcil encontrar ejemplos.

11

29. Sea L1 = {xnym | 1 < n m 2n } y L2 el lenguaje generado por la siguiente gramtica. Se cumple que

S AA xAA BB xBB

y

yy

a) L1 = L2

b) L1 L2 c) L1 L2 Solucin: B. La gramtica genera cualquier cadena xnym aplicando 2nm veces la segunda regla y mn veces la cuarta; por tanto, L1 L2. Sin embargo, las cadenas , xy y xyy no pertenecen a L1, por lo que L1 L2. 30. El resultado de concatenar dos lenguajes independientes de contexto, es siempre un lenguaje independiente de contexto?

a) S, siempre

b) No, nunca

c) Depende de los casos Solucin: A.

31. Dados dos lenguajes independientes de contexto L1 y L2, existe una gramtica G tal que L(G) = L1 L2? a) S, siempre

b) No, nunca

c) Depende de los casos Solucin: A. L1 y L2, por ser independientes de contexto, son estructurados por frases y en consecuencia su interseccin tambin lo es. Todo lenguaje estructurado por frases es generado por una gramtica.

32. Sea el alfabeto {x, y}. Cuntas cadenas contiene el lenguaje aceptado por la mquina de Turing R? a) Ninguna

b) Varias (un nmero finito mayor que uno)

c) Infinitas Solucin: C. El lenguaje que acepta es *.

Septiembre 08, original

12

33. Indique cul de las siguientes equivalencias entre expresiones regulares es incorrecta:

a) 1* 1*0( 01)* = 1* b) 1*0 1*0(01)* (01) = 1*0(01)* c) 1* 1*0( 01)* = 1*( 0) Solucin: C.

34. Sean r y s expresiones regulares. Indique cul de las siguientes igualdades NO siempre se verifica:

a) (r s)* = (r*s*)* b) r* = r*r*

c) rsr=(rs)r Solucin: C. Sean r = a, s = b. La cadena aa es generada por (ab)a y no por aba 35. Indique cul de los siguientes lenguajes es regular:

a) {0 n | la raz cuadrada de n es un nmero entero}, = {0,1} b) {0 n | la raz cuadrada de n es un nmero entero}, = {0} c) El conjunto de 0s y 1s, comenzando por 1, tal que cuando se interpreta como un entero, dicho entero es un nmero primo menor que 300

Solucin: C. El lenguaje de la opcin C es un lenguaje finito y por tanto regular. El lenguaje {0 n | la raz cuadrada de n es un nmero entero} no es regular, independientemente del alfabeto considerado, ya que no cumple el lema de bombeo. Consideremos w = , w =xyz. Bombeando la subcadena y obtenemos la cadena xyyz, cuya longitud vara entre n

2

0n2 + 1 y 2n2. El siguiente cuadrado perfecto despus

de n2 es (n+1)2= n2+ 1+2n y, para todo nmero natural n, n2+ 1+2n > 2n2.

36. Un homomorfismo de cadenas es una funcin sobre cadenas que sustituye cada smbolo por una cadena determinada. As, la funcin h(0) = ab, h(1) = es un homomorfismo que asigna, p.e, a la cadena 0011 la cadena abab. Indique cul de las siguientes afirmaciones es falsa:

a) Si L es un lenguaje regular de alfabeto y h es un homomorfismo sobre , entonces h(L) tambin es regular

b) Si h(L) es un lenguaje no regular de alfabeto y h es un homomorfismo sobre , entonces L tambin es no regular

c) Si h(L) es un lenguaje regular de alfabeto y h es un homomorfismo sobre , entonces L tambin es regular

Solucin: C. Supongamos que el homomorfismo h asigna la cadena a cualquier smbolo del alfabeto. En este caso, h(L) sera el lenguaje regular {} independientemente de L. A es verdadera: basta con ver que dada una expresin regular r que define L, entonces h(r) define h(L). En cuanto a la opcin B, es obviamente verdadera pues, de otro modo, estara en contradiccin con la opcin A.

13

37. Sean L1 y L2 los lenguajes generados, respectivamente, por la gramtica SA1B, A 0A, A , B0B, B1B, B. y la expresin regular 0*1(01)*. Indique cul de las siguientes afirmaciones es cierta (donde denota la inclusin estricta): a) L1 = L2

b) L1 L2 c) L2 L1 Solucin: A.

38. Sea L1 = {an bn cm dm | n 1, m 1} {an bm cm dn | n 1, m 1} y L2 el lenguaje generado por la gramtica SAB, S C, A aAb, Aab, BcBd, Bcd, CaCd, CaDd, DbDc, Dbc. Indique cul de las siguientes afirmaciones es cierta (donde denota la inclusin estricta): a) L1 = L2

b) L1 L2 c) L2 L1 Solucin: A.

39. Indique cul de las siguientes afirmaciones es falsa: a) Para todo autmata finito existe una longitud mxima tal que las cadenas que acepta el autmata nunca exceden dicha longitud

b) Todo autmata determinista definido para un alfabeto con n smbolos debe contener al menos n transiciones

c) Sea n un nmero natural tal que n 2. El nmero total de mquinas de Turing con n estados es infinito

Solucin: A. Las cadenas han de ser de longitud finita, pero en general no existe una longitud mxima. B es verdadera: Un autmata determinista debe estar completamente definido (ver pg. 32 del libro de texto). C es falsa: es finito cuando fijamos el alfabeto y el conjunto de smbolos de cinta; sin estas restricciones, el nmero es infinito. (Esta observacin es importante para la demostracin del teorema 3.5.).

40. Indique cul de las siguientes afirmaciones es verdadera:

a) Una mquina de Turing universal es aqulla capaz de decidir cualquier lenguaje.

b) El problema de la parada consiste en decidir si una cadena de unos y ceros es la versin codificada de una mquina de Turing autoterminante.

c) Una mquina de Turing universal es aqulla capaz de implementar cualquier funcin.

Solucin: B. A y C son falsas: ver la pg. 184 del libro de texto.

14

41. Considere la mquina de Turing de la figura e indique cul de las siguientes afirmaciones es falsa:

x/R

x/R x/R y/R

z/R

z/R

z/R

x/R

x/R

a) La mquina es determinista

b) La mquina se detiene si y slo encuentra en la cinta la secuencia xyxz

c) La mquina nunca tiene una terminacin anormal

Solucin: B. La mquina no se detiene al leer la cadena xyxxyxz

42. En un cierto autmata de pila determinista con ={x, y} existe una transicin (i, , , j, x). Cuntas transiciones en total deben partir del estado i? a) Una

b) Dos

c) Ms de dos

Solucin: A. Est claro que, por ser determinista, la transicin (i, , , , ) excluye (i, x, , , ), (i, y, , , ), (i, , x, , ), (i, , y, , ), (i, x, x, , ), (i, x, y, , ), (i, y, x, , ) e (i, y, y, , ), es decir, no hay ms que una transicin desde el estado i.

43. Sea G una gramtica libre de contexto tal que slo existe una regla para cada no terminal. Es regular el lenguaje L(G)?

a) S, para todo G

b) No, nunca

c) Depende de G

Solucin: A. Porque L(G) contiene una sola cadena (o quiz ninguna, como es el caso de la gramtica SxS).

44. Indique cul de las siguientes afirmaciones es falsa: a) La unin de un nmero finito de lenguajes estructurados por frases es un lenguaje estructurado por frases

b) El complementario de la concatenacin de dos lenguajes estructurados por frases es igual a la concatenacin de los complementarios de ambos; es decir, L1, L2, c(L1 L2) = c(L1)c(L2)

c) Un lenguaje definido a partir de un alfabeto que contiene un solo smbolo puede no ser estructurado por frases

Solucin: B. Contraejemplo: L1={xy}, L2={z}. Por un lado, xyzc(L1L2) porque xyzL1L2 y, por otro, xyzc(L1)c(L2) porque x c(L1) e yzc(L2). A es verdadera: la unin de dos lenguajes estructurados por frases es un lenguaje

15

estructurado por frases. Esto puede demostrarse mediante gramticas, marcando cada terminal A de la i-sima gramtica como Ai y aadiendo una regla del tipo SSi por cada gramtica. Tambin se podra demostrar este resultado mediante mquinas de Turing, de modo semejante a como se hizo en la fig. 1.27 (pg. 59) del libro de texto para la unin de lenguajes regulares. C es verdadera: el conjunto de lenguajes de es no numerable (cada cadena puede hacerse corresponder con un nmero natural el que indica su longitud y el conjunto de partes de N es no numerable), mientras que el conjunto de lenguajes estructurados por frases es numerable.

45. Sea n un nmero primo. El lenguaje formado por todas las cadenas cuya longitud es mltiplo de n es

a) regular

b) independiente de contexto (en sentido estricto)

c) estructurado por frases (en sentido estricto)

Solucin: A. Supongamos, por ejemplo, que n=3. Para cada smbolo x del alfabeto escribimos cuatro reglas: SxS1, S1xS2, S2xS, S2x. Podamos demostrarlo tambin construyendo en vez de una gramtica regular un autmata finito.

46. Sea L el lenguaje del alfabeto = {0,1} cuyas cadenas tienen igual nmero de ceros que de unos, y tales que en cada prefijo la diferencia entre el nmero de 0s y el nmero de 1s sea a lo sumo de una unidad. Indique para qu valor de etiqueta L es reconocido por el autmata de la figura:

0

0 1 0

etiqueta

0

1

1

a) Etiqueta = 1

b) Etiqueta = 0

c) Ningn valor de etiqueta hace que L sea reconocido por el autmata.

Solucin: A.

47. Sea L el lenguaje de alfabeto = {a,b,c} y cadenas de forma wcv, donde w y v son cadenas de as y bs y w y v tienen la misma longitud pero v no es la cadena inversa de w. Dicho lenguaje coincide con el generado por la gramtica

a) S aSa, SbSb, SaRb, SbRa, RaRa, RbRb, RaRb, RbRa, Rc. b) S aSa, SbSb, SaRb, SbRa, RaRb, RbRa, Rc. c) S aSa, SbSb, SaRb, SbRa, RaRa, RbRb, Rc. Solucin: A. Como w y v no pueden ser cadenas inversas, al menos debe existir un par de caracteres de w y v que ocupen posiciones simtricas con respecto al centro de la cadena y sean diferentes. Por tanto, toda cadena de L puede ser generada por la

16

gramtica, y toda cadena generada por la gramtica pertenece a L. La respuesta B no es correcta porque esa gramtica no genera la cadena aacab, y la C no es correcta porque la gramtica no genera la cadena aacbb.

48. Se desea disear una mquina de Turing que multiplique por dos un nmero en base 10. Inicialmente el nmero se encontrara en la cinta (una cifra por casilla a partir de la segunda, en la primera casilla un carcter blanco, y el resto de la cinta tambin en blanco) y la cabeza de lectura sealara a la primera cifra del nmero. Al detenerse la mquina, se habra sustituido el nmero por el resultado, y la cabeza lectora sealara a la primera casilla de la cinta. Indique para qu valor de etiqueta la siguiente solucin sera correcta:

/ , L

0 / 0 , R 1 / 1 , R 2 / 2 , R 3 / 3 , R 4 / 4 , R

0 / 0 , L 1 / 2 , L 2 / 4 , L 3 / 6 , L 4 / 8 , L

5 / 0 , L 6 / 2 , L 7 / 4 , L 8 / 6 , L 9 / 8 , L

e t i q u e t a

5 / 1 , L 6 / 3 , L 7 / 5 , L 8 / 7 , L 9 / 9 , L

/ , R / 1 , L

5 / 5 , R 6 / 6 , R 7 / 7 , R 8 / 8 , R 9 / 9 , R

a) etiqueta = 0/1,L 1/3,L 2/5,L 3/7,L 4/9,L b) etiqueta = 0/1,R 1/3,R 2/5,L 3/7,R 4/9,R

c) etiqueta = /1,L Solucin: A.

Septiembre 08, reserva

49. Indique cul de las siguientes equivalencias entre expresiones regulares es incorrecta:

a) 01( 01) ( 01)* ( 01) = (01)* b) ( 01) ( 01)* = c) 01 ( 01) ( 01)* ( 01) =0 (01)*0 Solucin: C.

17

50. Sean r y s expresiones regulares. Indique cul de las siguientes propiedades siempre se verifica:

a) (r*s*)* = (rs)* b) (rs)* = r*s* c) (rsr)*rs=(rr*s)* Solucin: A. Sean r=a, s=b. Caso B: La cadena ab es generada por la expresin (ab)*

y no por a*b*. Caso C: es generada por la expresin (aa*b)* y no lo es por la expresin (aba)*ab.

51. Sea L1 = {aibjck} | ij o jk} y L2 el lenguaje generado por la siguiente gramtica: SAB, SCD, AaA, A, BbBc, BE, BcD, CaCb, CE, CaA, DcD, D, EbE, Eb. Indique cul de las siguientes afirmaciones es cierta (donde denota la inclusin estricta):

a) L1 = L2

b) L1 L2 c) L2 L1 Solucin: A. El no terminal A genera cero o ms as. D genera cero o ms cs. E genera

cero o ms bs. B genera primero un nmero igual de bs y cs, luego produce bien uno o ms bs (via E) o uno o ms cs (via cD). Es decir, B genera cadenas en b*c* con un nmero diferente de bs y cs. Similarmente, C genera un nmero diferente de as y bs, mientras que CD genera cadenas de a*b*c* con un nmero diferente de as y bs.

52. Sea L un lenguaje definido a partir de un alfabeto que contiene un solo smbolo. Cul de las siguientes afirmaciones es cierta?

a) L es necesariamente un lenguaje regular.

b) L es necesariamente un lenguaje independiente de contexto, pero quiz no regular

c) Ninguna de las anteriores.

Solucin: C. Contraejemplo: L puede ser el lenguaje formado por todas las cadenas cuya longitud es un nmero primo.

53. Cul es el nmero mximo de transiciones para un autmata de pila con n estados, s smbolos en el alfabeto y g smbolos de pila?

a) n2(s+1)2g

b) n2(s+1)2(g+1).

c) n2(s+1)(g+1)2.

Solucin: C. El conjunto de transiciones de un autmata de pila no-determinista es un subconjunto de S S ( { ( { ( { }) }) }) .

54. Sean L1 el lenguaje generado por la gramtica situada a la izquierda y L2 el lenguaje generado por la gramtica situada a la derecha.

18

S xAA xAB yB

ByzSBz

yzyAyzSz

S xAS xA xA yA

Indique cul de las siguientes afirmaciones es cierta (donde denota la inclusin estricta):

a) L1 = L2

b) L1 L2 c) L2 L1 Solucin: A. Basta sustituir el no-terminal B por las secuencias que puede generar.

55. Sea M un autmata de pila que contiene la transicin (i, y, , j, ); sea M el autmata resultante de sustituir dicha transicin por (i, y, x, j, x). Cul de las siguientes afirmaciones es cierta?

a) L(M) = L(M)

b) L(M) L(M) c) L(M) L(M) Solucin: C. El nmero de cadenas aceptadas puede disminuir, pero nunca puede

aumentar.

56. En un cierto autmata de pila determinista con ={x, y} existe una transicin (i, x, , j, ). Cuntas transiciones en total deben partir del estado i? a) Una.

b) Dos.

c) Dos o ms.

Solucin: C. Para que el autmata pueda leer una y de la cadena de entrada, hace falta que exista una transicin de la forma (i, y, , , ) o dos transiciones (i, y, x, , ) e (i, y, y, , ); es decir, son dos o tres en total.

57. Sean = {x} y L = {cadenas de longitud impar}. Queremos construir una mquina de Turing M tal que L(M) = L. Indique qu valor de la variable etiqueta hace correcta la siguiente solucin: x/R

/R x/R

etiqueta a) etiqueta = /R b) etiqueta = /

19

c) Ningn valor de etiqueta hace correcta la solucin

Solucin: C. Porque del estado de parada no puede salir ningn arco.

58. Sea el alfabeto {x, y}. Cuntas cadenas contiene el lenguaje aceptado por la mquina de Turing R? a) Ninguna

b) Varias (un nmero finito mayor que uno)

c) Infinitas

Solucin: C. El lenguaje que acepta es *. 59. Indique cul de las siguientes afirmaciones es falsa: a) Una mquina de Turing puede aceptar una cadena de longitud infinita

b) El conjunto de lenguajes estructurados por frases es no numerable

c) Dada una gramtica estructurada por frases, es posible que exista un autmata finito no determinista que acepte el mismo lenguaje

Solucin: B. El conjunto de lenguajes estructurados por frases es numerable. A es verdadera: una mquina de Turing es capaz de aceptar una cadena sin leer todos sus smbolos. C es verdadera: toda gramtica regular G es estructurada por frases y, a la vez, existe una autmata finito determinista que acepta el mismo lenguaje que G.

60. Cuntas cadenas de longitud 6 representa la expresin regular x(yz)x(xyz)*x? a) Menos de 10

b) 10

c) Ms de 10

Solucin: C. Son las 233=18 cadenas representadas por la expresin regular x(yz)x(xyz)(xyz)x.

20

61. Sean L el lenguaje generado por la expresin regular b(0 1)* (b bb) (b bb). Indique para qu valor de etiqueta L es reconocido por el autmata de la figura:

b

etiqueta b

0 1

a) Etiqueta = b) Etiqueta = b

c) Ningn valor de etiqueta hace que L sea reconocido por el autmata.

Solucin: B.

62. Indique cul de las siguientes afirmaciones es verdadera:

a) La unin de infinitos conjuntos NO regulares NO puede ser regular

b) La estrella de Kleene de un lenguaje NO regular puede ser regular

c) Un conjunto cuyo complementario sea finito puede NO ser regular

Solucin: B. La unin de infinitos conjuntos no regulares puede ser regular ( la unin infinita de los lenguajes Lm= xnyn+m es un lenguaje regular). Un conjunto cuyo complementario sea finito (L) puede expresarse como diferencia entre dos conjuntos regulares (S*-L), y por tanto es regular. La estrella de Kleene de un lenguaje no regular puede ser regular (p.e. dado L = {xn, | n nmero primo}, L* es regular).

63. Indique cul de las siguientes afirmaciones es falsa: a) Sea L={a, ba}. L puede ser aceptado por un autmata de pila determinista que siempre llegue a los estados de aceptacin con pila vaca

b) Sea L={a, ab}. L puede ser aceptado por un autmata de pila determinista que siempre llegue a los estados de aceptacin con pila vaca

c) Si M es un autmata de pila determinista que siempre llega a los estados de aceptacin con pila vaca, entonces L(M) no puede ser aceptado por un autmata de pila no determinista

Solucin: C. A y B son ciertas, ya que L es un lenguaje regular. C es falsa: para todo lenguaje reconocido por un autmata de pila determinista existe un autmata de pila determinista que lo reconoce y acepta.

21

64. Indique para qu valor de la variable etiqueta el autmata de la figura reconoce al lenguaje representado por la expresin regular 1(00 1)*((10)* 101)*

1 0

0

0 1

1

1 1

etiqueta

0 1

a) etiqueta = 0 b) etiqueta = 1

c) etiqueta = Solucin: B.

1. Indique cul de las afirmaciones siguientes es FALSA:a) Un autmata finito determinista utilizado como reconocedor de lenguajes con al menos una cadena necesariamente tiene que tener al menos un estado de aceptacin b) Dada una gramtica regular G, siempre existe un autmata finito M tal que L(G) = L(M) y M tiene un nico estado de aceptacinc) Un autmata reconoce una cadena cuando alcanza un estado de aceptacin durante su lectura

2. Indique cul de los siguientes lenguajes NO es regular:a) L =(anbm ( n+m > 5, n > 0, m ( 0(b) L =(anbm ( m > 5n, n > 0(c) L =(an ( n/10 es un entero(

3. Sean L1 y L2 los lenguajes aceptados, respectivamente, por los autmatas de las figuras 1) y 2). Indique cul de las siguientes afirmaciones es cierta:a) L1 = L2, uno de los dos autmatas es determinista y el otro no lo es.b) L1 = L2, si consideramos que uno de los diagramas est incompleto.c) L1 ( L2 Solucin: C. El autmata de la figura 2 no acepta la cadena abb, mientras que el de la figura 1) s la acepta.

4. Indique cul de las siguientes gramticas genera el lenguaje L = (amb2mc2n ( m >0, n ( 0(a) S ( AB, A ( aAb ( ab, B ( bBc ( (b) S ( AB, A ( aAbb ( abb, B ( cBc ( (c) Las dos gramticas anteriores generan el lenguaje L

5. Considere el lenguaje 2-menos(L) = (w ( vw ( L y (v( = 2(, v, w ( (*, (= (a,b(. Indique cul de las siguientes afirmaciones es FALSA.a) Si L es un lenguaje regular entonces 2-menos(L) es regularb) Aunque L sea regular, es posible que 2-menos(L) no sea regularc) Aunque L no sea regular 2-menos(L) puede ser regular

6. Indique cul de las siguientes afirmaciones, referidas a la estrella de Kleene de un conjunto, es FALSA:a) La estrella de Kleene de un alfabeto (, ( *, es el lenguaje de todas las cadenas que se pueden formar con smbolos de (, incluyendo la cadena vaca.b) x ( ( * significa que x es una cadena formada con smbolos de (, o bien la cadena vacac) La estrella de Kleene de un conjunto siempre es un conjunto infinito

7. Sean L1, L2 y L3 los lenguajes reconocidos, respectivamente, por los autmatas de las figuras 1), 2) y 3). Indique cul de las siguientes afirmaciones es verdadera. a) L3 = L1 ( L2 b) L3 = L1 ( L2 c) L3 ( L1 ( L2

8. Indique cul de las siguientes afirmaciones sobre el lema de bombeo para lenguajes regulares es verdadera:a) No lo cumple el lenguaje de palndronos de longitud par, pero lo cumple el lenguaje de palndronos de longitud imparb) Se refiere a lenguajes infinitos; de hecho, todo lenguaje finito lo cumple de forma trivial c) Puede utilizarse para demostrar que un lenguaje es regular, pero no para demostrar que un lenguaje no es regular.Solucin: B. Se cumple de forma trivial en el caso de los lenguajes finitos: dado que siempre puede encontrarse una constante k mayor que cualquier cadena del lenguaje, claramente ser cierto que para toda cadena de la forma xyz ( L con |y| ( k, " ya que no hay cadenas en L tal que |y| ( k. El lema de bombeo puede utilizarse para demostrar que un lenguaje no es regular, pero no para demostrar que un lenguaje es regular, ya que existen lenguajes que verifican el lema de bombeo y, sin embargo, no son regulares.

9. Sea un lenguaje L que puede expresarse como concatenacin de dos lenguajes L1 y L2. Sean G1(S1,T1,V1,R1) y G2(S2,T2,V,R2), T1 ( T2 = (, a) G( S,T,V,R) donde R = R1 ( R2 ( S (S1S2 es siempre una gramtica para Lb) G( S,T,V,R) donde R = R1 ( R2 ( S (S1S2 ( S ( ( es siempre una gramtica para Lc) La gramtica G no puede deducirse a partir de las gramticas G1 y G2

10. Indique cul de las siguientes afirmaciones es FALSA:a) Los lenguajes regulares podran ser aceptados por mquinas de Turing que siempre moviesen su cabeza a la izquierda.b) En realidad una mquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autmata finito principalmente en el mecanismo de aceptacin de cadenas: una mquina de Turing entra en un estado de aceptacin en cuanto concluye sus clculosc) Una mquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autmata finito principalmente en que tiene poder de escribir en su cinta, y por tanto almacenar datos a modo de un autmata de pila y reconocer lenguajes independientes del contexto.

11. Sea L un lenguaje regular y L = {x | x( L y la longitud de x es un nmero par}. Es L regular?a) L es regular cualquiera que sea L. b) L nunca es regular.c) Depende de L.

12. La concatenacin de dos lenguajes de es un subconjunto de13. El lenguaje generado por la siguiente gramtica esa) regular.b) independiente del contexto (en sentido estricto).c) estructurado por frases (en sentido estricto).

14. Indicar si la expresin regular (x ( y)(x ( y)* representa el mismo lenguaje que acepta el siguiente autmata.a) Verdadero b) Falsoc) Depende del alfabeto

15. Sea L un lenguaje generado por una gramtica libre de contexto en forma normal de Chomsky. Existe otra gramtica en forma normal de Chomsky que genere el complemento de L?a) S, para todo G.b) No, nunca.c) Depende de G.

16. Los palndromos (palabras capicas) del idioma castellano, tales como a, y, dad, oso, erre, etc., constituyen una) lenguaje regular.b) lenguaje independiente del contexto (en sentido estricto).c) lenguaje estructurado por frases (en sentido estricto).

17. Indique cul de los siguientes lenguajes es independiente del contexto:a) L = ( anbmc2nd2n ( n > 0, m > 0(b) L = ( (ab)ncndm ( n > 0, m > 0, n ( m(c) L = ( a2nbmcn ( n > 0, m ( 0, n es par y m es impar(

18. Un hombre que viaja con un lobo, una cabra y un repollo desea cruzar un ro. Dispone de una barca donde slo caben l y una de sus posesiones a la vez. Si dejara solos al lobo y la cabra el lobo comera a la cabra, y si dejara solos a la cabra y al repollo la cabra comera el repollo. Muestra el siguiente autmata todas las secuencias posibles de cruces del ro mediante las cuales el hombre consigue pasar a la otra orilla con todas sus pertenencias? (l: el hombre cruza con el lobo; c: el hombre cruza con la cabra; r: el hombre cruza con el repollo; s: el hombre cruza slo; l: el hombre regresa a la orilla de partida con el lobo; c: el hombre regresa a la orilla de partida con la cabra; r: el hombre regresa a la orilla de partida con el repollo; s: el hombre regresa a la orilla de partida slo.).a) S las muestra, pero el diagrama est incompletob) S las muestra, y el diagrama est completoc) No las muestra

19. Considere el autmata M = (Q, (, (, q0, F), dondea) M es no deterministab) M reconoce el lenguaje L = {wa | w ( {a,b}*}c) La funcin ( no define un autmata finito correcto

20. Sean L1 = {0x | x ( {0,1}*} y L2 = {x0 | x ( {0,1}*}. Sea L el lenguaje reconocido por el autmata de la figura. Considere el alfabeto ( = {0,1}. a) L = L1 ( L2 b) L = L1 ( L2c) L es el lenguaje complementario de L1 en ( *

21. Indique cul de las siguientes afirmaciones, relativas a la estrella de Kleene de un lenguaje L es verdadera:a) El conjunto de cadenas que pueden formarse concatenando cualquier nmero de cadenas cada una de las cuales pertenece a L ( {(}.b) L* = {wn | n ( 0 y w ( L}c) Para todo L que contenga al menos una cadena L* es infinito

22. Considere la siguiente gramtica e indique cul de las siguientes afirmaciones es FALSA:a) Todas las frases generadas mediante la gramtica son frases gramaticalmente correctas en castellanob) Muchas de las frases generadas no son gramaticalmente correctas en castellanoc) El castellano no puede generarse mediante una gramtica estructurada por frases de reglas sencillas como si de un lenguaje formal se tratase

23. Sea un lenguaje L que puede expresarse como unin de dos lenguajes L1 y L2. Sean G1(S1,T1,V1,R1) y G2(S2,T2,V,R2), T1 ( T2 = (, a) G( S,T,V,R) donde R = R1 ( R2 ( S ( S1 | S2 es siempre una gramtica para Lb) G( S,T,V,R) donde R = R1 ( R2 ( S ( S1 | S2 ( S ( ( es siempre una gramtica para Lc) La gramtica G no puede deducirse de las gramticas G1 y G2

24. Indique cul de las siguientes afirmaciones es verdadera:a) Un autmata finito nunca puede meterse en un ciclo que se ejecute indefinidamenteb) Un autmata de pila determinista nunca puede meterse en un ciclo que se ejecute indefinidamentec) Una mquina de Turing determinista puede meterse en un ciclo que se ejecute indefinidamente.

25. Indique cul de las siguientes afirmaciones es verdadera:a) Con una nica mquina de Turing pueden reconocerse tres lenguajes: el lenguaje de las cadenas que acepta, el lenguaje de las cadenas que rechaza y el lenguaje de las cadenas que llevan a la mquina a un bucle de ejecucin infinita.b) Es posible disear una mquina de Turing de tres cintas que reconozca tres lenguajes.c) Con una nica mquina de Turing, ya sea de una o varias cintas, determinista o no determinista, slo es posible reconocer un lenguaje

26. Indique cul de las siguientes afirmaciones, referidas a la mquina de Turing de la figura es FALSA:a) La mquina implementa la funcin f(anbm) = ambn, n>0, m>0.b) Si la mquina se arranca con la cabeza de lectura apuntando al primer smbolo empezando por la izquierda de aabbbb la mquina se detiene con la cabeza de lectura apuntando al primer smbolo empezando por la izquierda de aaaabb.c) La mquina llega a un estado de parada sea cual sea la configuracin inicial de cinta.

27. El lenguaje xmynzp, donde m, n y p son enteros no negativos tales que m+n=p, es...a) regular.b) independiente del contexto (en sentido estricto).c) estructurado por frases (en sentido estricto).

28. Un lenguaje generado por una gramtica independiente de contextoa) es siempre regularb) nunca es regularc) depende de los casos

29. Sea L1 = {xnym | 1 < n ( m ( 2n } y L2 el lenguaje generado por la siguiente gramtica. Se cumple quea) L1 = L2b) L1 ( L2c) L1 ( L2Solucin: B. La gramtica genera cualquier cadena xnym aplicando 2n(m veces la segunda regla y m(n veces la cuarta; por tanto, L1 ( L2. Sin embargo, las cadenas , xy y xyy no pertenecen a L1, por lo que L1 ( L2.

30. El resultado de concatenar dos lenguajes independientes de contexto, es siempre un lenguaje independiente de contexto?a) S, siempreb) No, nuncac) Depende de los casos

31. Dados dos lenguajes independientes de contexto L1 y L2, existe una gramtica G tal que L(G) = L1 ( L2?a) S, siempreb) No, nuncac) Depende de los casos

32. Sea el alfabeto {x, y}. Cuntas cadenas contiene el lenguaje aceptado por la mquina de Turing (R?a) Ningunab) Varias (un nmero finito mayor que uno)c) Infinitas

33. Indique cul de las siguientes equivalencias entre expresiones regulares es incorrecta:a) 1* ( 1*0((( 0(1)*( = 1*b) 1*0 ( 1*0(((0(1)* (((0(1) = 1*0(0(1)*c) 1* ( 1*0((( 0(1)*( = 1*((( 0)

34. Sean r y s expresiones regulares. Indique cul de las siguientes igualdades NO siempre se verifica:a) (r( s)* = (r*s*)*b) r* = r*r*c) r(sr=(r(s)r

35. Indique cul de los siguientes lenguajes es regular:a) {0 n | la raz cuadrada de n es un nmero entero}, ( = {0,1}b) {0 n | la raz cuadrada de n es un nmero entero}, ( = {0}c) El conjunto de 0s y 1s, comenzando por 1, tal que cuando se interpreta como un entero, dicho entero es un nmero primo menor que 300

36. Un homomorfismo de cadenas es una funcin sobre cadenas que sustituye cada smbolo por una cadena determinada. As, la funcin h(0) = ab, h(1) = ( es un homomorfismo que asigna, p.e, a la cadena 0011 la cadena abab. Indique cul de las siguientes afirmaciones es falsa:a) Si L es un lenguaje regular de alfabeto ( y h es un homomorfismo sobre (, entonces h(L) tambin es regularb) Si h(L) es un lenguaje no regular de alfabeto ( y h es un homomorfismo sobre (, entonces L tambin es no regularc) Si h(L) es un lenguaje regular de alfabeto ( y h es un homomorfismo sobre (, entonces L tambin es regular

37. Sean L1 y L2 los lenguajes generados, respectivamente, por la gramtica SA1B, A 0A, A (, B0B, B1B, B(. y la expresin regular 0*1(0(1)*. Indique cul de las siguientes afirmaciones es cierta (donde ( denota la inclusin estricta):a) L1 = L2b) L1 ( L2c) L2 ( L1

38. Sea L1 = {an bn cm dm | n (1, m (1} ( {an bm cm dn | n (1, m (1} y L2 el lenguaje generado por la gramtica SAB, S C, A aAb, Aab, BcBd, Bcd, CaCd, CaDd, DbDc, Dbc. Indique cul de las siguientes afirmaciones es cierta (donde ( denota la inclusin estricta):a) L1 = L2b) L1 ( L2c) L2 ( L1

39. Indique cul de las siguientes afirmaciones es falsa:a) Para todo autmata finito existe una longitud mxima tal que las cadenas que acepta el autmata nunca exceden dicha longitudb) Todo autmata determinista definido para un alfabeto con n smbolos debe contener al menos n transicionesc) Sea n un nmero natural tal que n (2. El nmero total de mquinas de Turing con n estados es infinito

40. Indique cul de las siguientes afirmaciones es verdadera:a) Una mquina de Turing universal es aqulla capaz de decidir cualquier lenguaje.b) El problema de la parada consiste en decidir si una cadena de unos y ceros es la versin codificada de una mquina de Turing autoterminante.c) Una mquina de Turing universal es aqulla capaz de implementar cualquier funcin.

41. Considere la mquina de Turing de la figura e indique cul de las siguientes afirmaciones es falsa: a) La mquina es deterministab) La mquina se detiene si y slo encuentra en la cinta la secuencia xyxz c) La mquina nunca tiene una terminacin anormal

42. En un cierto autmata de pila determinista con ={x, y} existe una transicin (i, , , j, x). Cuntas transiciones en total deben partir del estado i?a) Unab) Dosc) Ms de dos

43. Sea G una gramtica libre de contexto tal que slo existe una regla para cada no terminal. Es regular el lenguaje L(G)?a) S, para todo Gb) No, nuncac) Depende de G

44. Indique cul de las siguientes afirmaciones es falsa:a) La unin de un nmero finito de lenguajes estructurados por frases es un lenguaje estructurado por frasesb) El complementario de la concatenacin de dos lenguajes estructurados por frases es igual a la conca tenacin de los complementarios de ambos; es decir, (L1, (L2, c(L1 L2) = c(L1)c(L2)c) Un lenguaje definido a partir de un alfabeto que contiene un solo smbolo puede no ser estructurado por frases

45. Sea n un nmero primo. El lenguaje formado por todas las cadenas cuya longitud es mltiplo de n esa) regularb) independiente de contexto (en sentido estricto)c) estructurado por frases (en sentido estricto)

46. Sea L el lenguaje del alfabeto ( = (0,1( cuyas cadenas tienen igual nmero de ceros que de unos, y tales que en cada prefijo la diferencia entre el nmero de 0s y el nmero de 1s sea a lo sumo de una unidad. Indique para qu valor de etiqueta L es reconocido por el autmata de la figura: a) Etiqueta = 1b) Etiqueta = 0c) Ningn valor de etiqueta hace que L sea reconocido por el autmata.

47. Sea L el lenguaje de alfabeto ( = {a,b,c} y cadenas de forma wcv, donde w y v son cadenas de as y bs y w y v tienen la misma longitud pero v no es la cadena inversa de w. Dicho lenguaje coincide con el generado por la gramticaa) S ( aSa, S(bSb, S(aRb, S(bRa, R(aRa, R(bRb, R(aRb, R(bRa, R(c.b) S ( aSa, S(bSb, S(aRb, S(bRa, R(aRb, R(bRa, R(c.c) S ( aSa, S(bSb, S(aRb, S(bRa, R(aRa, R(bRb, R(c.

48. Se desea disear una mquina de Turing que multiplique por dos un nmero en base 10. Inicialmente el nmero se encontrara en la cinta (una cifra por casilla a partir de la segunda, en la primera casilla un carcter blanco, y el resto de la cinta tambin en blanco) y la cabeza de lectura sealara a la primera cifra del nmero. Al detenerse la mquina, se habra sustituido el nmero por el resultado, y la cabeza lectora sealara a la primera casilla de la cinta. Indique para qu valor de etiqueta la siguiente solucin sera correcta: a) etiqueta = 0/1,L 1/3,L 2/5,L 3/7,L 4/9,L b) etiqueta = 0/1,R 1/3,R 2/5,L 3/7,R 4/9,R c) etiqueta = (/1,L

49. Indique cul de las siguientes equivalencias entre expresiones regulares es incorrecta:a) (( 0(1(((( 0(1) ((( 0(1)* ((( 0(1) = (0(1)*b) ( ( ((( 0(1) ((( 0(1)*( = (c) (( 0(1( ((( 0(1) ((( 0(1)* ((( 0(1) =0 (0(1)*0

50. Sean r y s expresiones regulares. Indique cul de las siguientes propiedades siempre se verifica:a) (r*s*)* = (r(s)*b) (r(s)* = r*(s*c) (rs(r)*rs=(rr*s)*

51. Sea L1 = {aibjck} | i(j o j(k} y L2 el lenguaje generado por la siguiente gramtica: SAB, SCD, AaA, A(, BbBc, BE, BcD, CaCb, CE, CaA, DcD, D(, EbE, Eb. Indique cul de las siguientes afirmaciones es cierta (donde ( denota la inclusin estricta):a) L1 = L2b) L1 ( L2c) L2 ( L1

52. Sea L un lenguaje definido a partir de un alfabeto que contiene un solo smbolo. Cul de las siguientes afirmaciones es cierta?a) L es necesariamente un lenguaje regular.b) L es necesariamente un lenguaje independiente de contexto, pero quiz no regularc) Ninguna de las anteriores.

53. Cul es el nmero mximo de transiciones para un autmata de pila con n estados, s smbolos en el alfabeto y g smbolos de pila?a) n2(s+1)2gb) n2(s+1)2(g+1).c) n2(s+1)(g+1)2.

54. Sean L1 el lenguaje generado por la gramtica situada a la izquierda y L2 el lenguaje generado por la gramtica situada a la derecha.Indique cul de las siguientes afirmaciones es cierta (donde ( denota la inclusin estricta):a) L1 = L2b) L1 ( L2c) L2 ( L1

55. Sea M un autmata de pila que contiene la transicin (i, y, , j, ; sea M el autmata resultante de sustituir dicha transicin por (i, y, x, j, x. Cul de las siguientes afirmaciones es cierta?a) L(M) = L(M)b) L(M) ( L(M)c) L(M) ( L(M)

56. En un cierto autmata de pila determinista con ={x, y} existe una transicin (i, x, , j, ). Cuntas transiciones en total deben partir del estado i?a) Una.b) Dos.c) Dos o ms.

57. Sean = {x} y L = {cadenas de longitud impar}. Queremos construir una mquina de Turing M tal que L(M) = L. Indique qu valor de la variable etiqueta hace correcta la siguiente solucin: a) etiqueta = (/Rb) etiqueta = (/(c) Ningn valor de etiqueta hace correcta la solucin

58. Sea el alfabeto {x, y}. Cuntas cadenas contiene el lenguaje aceptado por la mquina de Turing (R?a) Ningunab) Varias (un nmero finito mayor que uno)c) Infinitas

59. Indique cul de las siguientes afirmaciones es falsa:a) Una mquina de Turing puede aceptar una cadena de longitud infinitab) El conjunto de lenguajes estructurados por frases es no numerablec) Dada una gramtica estructurada por frases, es posible que exista un autmata finito no determinista que acepte el mismo lenguaje

60. Cuntas cadenas de longitud 6 representa la expresin regular x(y(z)x(x(y(z)*x?a) Menos de 10 b) 10c) Ms de 10Solucin: C. Son las 2(3(3=18 cadenas representadas por la expresin regular x(y(z)x(x(y(z)(x(y(z)x.

61. Sean L el lenguaje generado por la expresin regular b(0 (1)* (b ( bb) ((b ( bb). Indique para qu valor de etiqueta L es reconocido por el autmata de la figura:a) Etiqueta = (b) Etiqueta = bc) Ningn valor de etiqueta hace que L sea reconocido por el autmata.

62. Indique cul de las siguientes afirmaciones es verdadera:a) La unin de infinitos conjuntos NO regulares NO puede ser regularb) La estrella de Kleene de un lenguaje NO regular puede ser regularc) Un conjunto cuyo complementario sea finito puede NO ser regular

63. Indique cul de las siguientes afirmaciones es falsa: a) Sea L={a, ba}. L puede ser aceptado por un autmata de pila determinista que siempre llegue a los estados de aceptacin con pila vaca b) Sea L={a, ab}. L puede ser aceptado por un autmata de pila determinista que siempre llegue a los estados de aceptacin con pila vaca c) Si M es un autmata de pila determinista que siempre llega a los estados de aceptacin con pila vaca, entonces L(M) no puede ser aceptado por un autmata de pila no determinista

64. Indique para qu valor de la variable etiqueta el autmata de la figura reconoce al lenguaje representado por la expresin regular 1(00 ( 1)*((10)* ( 101)* a) etiqueta = 0b) etiqueta = 1c) etiqueta = (Solucin: B.