Ingeniero Técnico en Informática de Sistemas

Computabilidad

Compartir 0 Me sirvió 0 No me sirvió

NOTA: Lo que aparece entre paréntesis es el número de veces que ha aparecido esa pregunta en distintos exámenes entre 1994 y 1999

1.- (x2) La Gramática G con las reglas de producción P={S::=aXbY, X::=aX|a, Y::=bY|b} La derivación de a1b3: SaXbYa2XbYa2Xb2Ya3Xb2Ya3Xb3a4b3

Es una derivación extrema izquierda

Es una derivación extrema derecha

Es una derivación intermedia

Ninguna de las respuestas es correcta.

2.- Dadas las gramáticas G1,G2,G3 y G4 con las reglas de producción:

P1={S::=AB, C::=a}

P2={S::=AB, B::=Ca, C::=a}

P3={S::=Sa}

P4={S::=a|b}

Todas definen el lenguaje vacío

G2 y G4 definen el lenguaje vacío

G1 y G2 definen el lenguaje vacío, pero G4 no

G2 y G4 definen el lenguaje vacío, pero G3 no

3.- Las gramáticas G1=({a,b,c.}, {S,,B}, S, P1) con P1={S::=abc|aAbc, Ab::=bA, Ac::=Bbcc, bB::=Bb, aB::=aaA|aa} y G2 = ({a,b}, {A}, S, {S::=ab|aSb}) son:

G1 es dependiente del contexto y G2 es independiente del contexto

G1 es independiente del contexto y G2 es dependiente del contexto

Ambas son independientes del contexto

G2 es independiente del contexto y G1 es dependiente del contexto

4.- La Máquina de Turing:

R R L2 R

Si se arranca con la cadena abab... termina con:

abab ...

aabab...

aba...

Ninguna de las anteriores

5.- Las Gramáticas G1=({a,b,c}, {S,A,B,C,D}, S, P1 ), G2=({a,b,c}, {S,A,B,C}, S, P2), G3=({a,b},{S,A,C, S, P3) con

P1={S::=aAAA, A::=aAb|aC, B::=BD|Ac, C::=b}

P2={S::=aAA, A::=aAb|aC, B::=Ac, C::=b}

P3={S::=aAA, A::=aAb|aC, C::=b}

G1 y G2 son equivalentes entre sí pero no con G3

G1 y G3 son equivalentes entre sí pero no con G2

G3 y G2 son equivalentes entre sí pero no con G1

Las tres son equivalentes

6.- Una Gramática estructurada por frases tiene reglas de producción de la forma:

::= con (T N )+ y (T N )*

AB::=v donde , (T N )*, v (T N )+ y A N

AB::=v donde , (T N )+, v (T N )* y A N

aB::=v donde , (T N )*, v (T N )+ y A T

7.- (x2)La función f: 3 esta definida por medio de recursividad primitiva a partir de las funciones:

g=mult(x,y) y por a=suma (41 x 41) la función f será:

x+xzy

zx+xy

x+xy

Ninguna de las anteriores es correcta

8.- (x3) La máquina de turing que calcula la función f((ab)n) =(ab)n-1

M=({a,b,}, {a,b}, , {q1,q2,q3,q4,q5}, q1,q5,f)

F(q1,a)=q2,a,R

F(q2,b)=q1,b,R

F(q1,)=q3,a,R

F(q3,)=q4,b,R

F(q1,b)=q5,b,P

F(q2,a)=q5,a,P

F(q3,a)=q5,a,P

F(q3,b)=q5,b,P

La complejidad temporal para la entrada (ab)n es:

n2+n-2

n+1

2n+2

Ninguna de las respuestas es correcta

9.- (x2)La frase “Toda función recursiva primitiva es computable por una Máquina de Turing”

Es verdadera siempre que se trabaje con máquinas de turing de 3 cintas

Es falsa, ya que las funciones computables por MT deben ser totales

Es falsa, ya que existen funciones recursivas primitivas que no son computables por MT

Ninguna de las respuestas anteriores es correcta

Mod (x/y) si y 0

10.- La función resto (x,y)= viene dada por las ecuaciones:

X si y=0

resto (0,y)=0

resto (x+1,y)= ((resto(x,y)+1) * ¬ eq (resto (x,y)+1, y)

resto (0,y)=0

resto (x+1,y)= ((resto(x,y)+1) * eq (resto(x,y)+1,y)

resto (0,y)=0

resto (x+1,y)= ((resto (x,y)+1) * ¬ eq (resto (x,y),y)

Ninguna de las anteriores

11.- La Maquina de Turing

	0	1
Q0		Q1 0 R
Q1	Q5 0 R	Q2 0 R
Q2	Q4 0 P	Q3 0 R
Q3	Q4 1 L	Q3 1 R
Q4	H 0 R	Q4 1 L
Q5	Q6 0 L	Q5 1 R
Q6		Q4 o L

Con una cinta de entrada 0 1(n1) 0 1(n2) 0 produce una salida:

Ninguna de las respuestas es correcta

0 1(n1+ n2) 0

0 1(n1+ n3-3) 0

0 1 (n1 + n2 - 2 ) 0

12.- La Gramática G=({A,B,S}, {a,b}, S, {S::=aA|aB, A::=bA|, B::=aB|})

no es regular y es ambigua

es regular y es ambigua

no es regular y no es ambigua

es regular y no es ambigua

13.- La máquina de Turing S4R si se arranca con la configuración inicial ( xyyqxx ) se para con la configuración final:

Ninguna de las respuestas es correcta

( q xx )

( q x )

14.- (x4)Si se pone en marcha la maquina de Turing de la figura con la configuración inicial ByyxBBxxxByyxxBB...

y x

x y

y B

I IB I B

Las complejidades temporal y espacial son iguales

La complejidad temporal es 16 y la complejidad espacial es 10

La complejidad temporal es 14 y la complejidad espacial es 10

Ninguna de las anteriores

15.- (x4)La clase NP

Está formada por los lenguajes aceptables por las máquinas de Turing en tiempo No Polinómico, por tanto, todo lenguaje a la clase P o a la clase NP

Engloba a la clase P

Engloba a las máquinas de Turing No Deterministas en tiempo Polinómico

No cumple ninguna de las propiedades anteriores o cumple más de una

16.- (x2)Las funciones recusivas parciales:

Son computables por MT Deterministas

Son computables por MT No Deterministas pero no son computables por MT Deterministas

No son todas computables por Máquinas de Turing

No cumplen ninguna de las propiedades anteriores o cumplen más de una

17.- (x6) Las máquinas compuestas DI y ID

Tienen el mismo comportamiento en todos los casos, además, no modifican la entrada

Se comportan de la misma forma en todos los casos salvo en uno

No existen

Ninguna de las respuestas anteriores es cierta

18.- (x4)La frase “Existen lenguajes aceptables por Máquinas de Turing Deterministas en tiempo polinómico que no son decidibles por Máquinas de Turing Deterministas en tiempo polinómico” es:

Verdadera porque existe un lenguaje L1 que es aceptable pero no decidible

Verdadera porque no todos los lenguajes aceptables son decidibles en tiempo polinómico

Falsa

Verdadera o Falsa dependiendo del lenguaje considerado

19.-(x3) La gramática SxSy; xSNxx; Ny

Genera el lenguaje {(yxxy)n, n }

Genera el lenguaje {xnyxxyn, n }

Genera el lenguaje {xn-1yxxyn, n }

Ninguno de los anteriores

20.- (x3)En la simulación de las Máquinas de Turing No Deterministas mediante Máquinas de Turing Deterministas, se utilizan tres cintas: La primera mantiene la cinta con la cadena de entrada sin modificar, en la segunda se copia la cadena de entrada para realizar cálculos auxiliares, y la tercera:

Se utiliza para chequear si los caminos generados llegan al estado de parada.

Se utiliza para generar las distintas secuencias de caminos, simular dichos caminos, y comprobar si se llega al estado de parada

Chequea que el número de pasos ejecutados no exceda el límite permitido

No se utiliza, o se utiliza para fines distintos de los mencionados

21.- (x3)En la simulación de una máquina de Turing M de k-cintas mediante una máquina de Turing M' de 1 cinta

Un estado compuesto refleja el estado de la máquina M junto los k símbolos que se encuentran bajo las cabezas de lectura/escritura de cada cinta

Un estado compuesto se produce al acceder a una celda en blanco en un movimiento en la derecha (en cuyo momento se sustituye dicha celda por una 2k-tupla de espacios en blanco) o al intentar ir a la izquierda encontrando el símbolo #

Un estado compuesto está formado por una tupla de k+1 elementos

Ninguna de las respuestas anteriores o más de una

22.- Sea L un lenguaje aceptable pero no decidible, entonces:

Existe una máquina de Turing que acepta todas las cadenas que pertenecen a L

No existe ninguna máquina de Turing que acepte las cadenas que no pertenecen a L

Las máquinas de Turing que lo aceptan son polinómicas

Ninguna de las anteriores o más de una de las anteriores es cierta

23.- (x3)Dada la siguiente Máquina de Turing No Determinista:

a,b

a,b w

D D w

B B

Reconoce el lenguaje “ {a,b}* contiene un símbolo repetido”

Reconoce el lenguaje “ {a,b}* acaba con `aa' o con `bb'

Reconoce cualquier cadena formada por símbolos `a' y `b'

Ninguno de los anteriores

0 si x=0 x " 2

24.- La función f2(x,y)= es construida por:

1 si x=1

pred (z) MULT [GE (z-x)] =0

pred (z) MULT [x, GE (2-z, x)] =0

(z) MULT [x, GE(2-z,x)] = 0

Ninguna de las anteriores o más de una.

25.- La sentencia FOR del lenguaje Pascal, ¿es una macro-sentencia en el lenguaje de los while-programas?

Sí, siempre que no se utilicen macro-test

No, ya que el while-programa equivalente utiliza otras macro-sentencias

Sí, ya que se puede encontrar un while-programa equivalente

Ninguna de las anteriores o más de una.

26.- Si una función parcial no es computable, entonces:

Es igual a la función semántica del while-programa que la computa

Aunque se puede definir de forma algorítmica, el while-programa que la computa no acaba

Según la tesis de Church no es recursiva parcial

Ninguna de las anteriores o más de una

27.- Según el intérprete construido:

Se ejecuta primero el analizador léxico y, a continuación, el analizador sintáctico

El analizador sintáctico se encarga de devolver los diferentes tokens al intérprete

El analizador sintáctico utiliza al analizador léxico a lo largo de la fase de interpretación

Ninguna de las anteriores o más de una de las anteriores

28.- El operador ¿es asociativo?

Sí

No, porque no está definido cuando el segundo operando es mayor que el primero

No, por una razón distinta a la anterior

Ninguna de las anteriores o más de una de las anteriores

29.- (x2)Dado n=129, Al concatenar head(n) con tail(n) se obtiene el número:

120

129

Ninguna de las anteriores o más de una.

30.- (x3) Si la función f: 3 se define mediante recursividad primitiva mediante las dos funciones:

g=K

h= mult ° (
x
) entonces la función f(x,y,z) es igual a

x y z

xyz

Ninguna de las anteriores

31.- Al ejecutar la máquina de Turing DBDBSBIB con la configuración BholaBholaB, se detiene con:

BholaBolaB

BBholaBolaB

BholaBBolaB

Ninguna de las anteriores

32.- (x2)Al ejecutar la máquina de Turing SI con la configuración: B1111B1111B, la complejidad espacial es:

Ninguna de las anteriores

33.- (x3)La gramática SxN; NSx; xNxy; genera el lenguaje;

{xnyxn: n +}

{xny: n +}

{xnyxn-1 +}

Ninguno de los anteriores

34.- (x2)Dada al función f, se define O(f) como:

El conjunto de funciones g para las cuales c, n0 tales que f(n)" c g(n) " n>n0

El conjunto de funciones g para las cuales c, n0 tales que g(n) " c f(n) " n>n0

El conjunto de funciones con la misma tasa de crecimiento que f

Ninguna de las anteriores o más de una de las anteriores.

35.- La función f(1, 2, 3)=3 puede ser computada mediante la máquina de Turing:

DBSIDBDBSIISIISI

¬ B

DBDBISI

DBSIDBSII

Ninguna de las anteriores o más de una de las anteriores

36.- La clase P:

Está formada por el conjunto de lenguajes aceptables por las máquinas de Turing Deterministas en tiempo polinómico

Está formada por el conjunto de lenguajes decidibles por las máquinas de Turing Deterministas en tiempo polinómico

Está formada por el conjunto de lenguajes aceptables por máquinas de Turing (Deterministas o no) en tiempo polinómico

Ninguna de las anteriores o más de una

37.- Cualquier lenguaje L:

O está en P o está en NP, pero no en ambos

O es decidible o aceptable

O es aceptable o no es aceptable

Ninguna de las anteriores o más de una

38.- La siguiente máquina de Turing:

x y y

D D D D

B,y B,y B,x

Reconoce el lenguaje x*yy(x|y)

Reconoce el lenguaje x*yy

Reconoce el lenguaje formado por las cadenas (x|y)* que contienen la subcadena xyy

Ninguna de las anteriores o más de una

39.- La frase “Toda función recursiva parcial es computable por Máquinas de Turing”:

Es verdadera, siempre que se trabaje con máquinas de Turing de 3 cintas.

Es falsa, las funciones computables por máquinas de Turing deben ser totales

Es falsa, ya que existen funciones que no son computables por máquinas de Turing

Ninguna de las anteriores o más de una

40.- La definición de un while-programa nos permite:

Asociar a cada while-programa la función parcial que computa

Conocer las reglas de escritura del lenguaje de los while-programas mediante la notación BNF

Definir las operaciones válidas sobre un conjunto de datos

Ninguna de las anteriores o más de una

41.- Si la función g: j es while-computable entonces:

La función g está definida para toda tupla de j números

Existe un único programa que computa g

Existe una secuencia de while-programas po,p1,p2, ... tal que g=fp0 =f p1=fp2=...

Ninguna de las anteriores o más de una de las anteriores

42.- (x3)La función f:2 computada por el siguiene while-programa

BEGIN

WHILE X2 X3 DO X3:=SUCC(X3);

X1:=PRED(X3);

END

Es f(x,y)=y 1

Es f(x,y)=y x

No está definida, puesto que no se conoce el valor de X3

Ninguna de las anteriores o mas de una

x si x"y

43.- (x2)La función: max(x,y) = se puede expresar como:

y si y<x

max(x,y)=x y

max(x,y)=(x y) + x

max(x,y)=x + (y x)

Ninguna de las anteriores o más de una

y si x=0 x=1

44.- La función f1(x,y)=

" en caso contrario

(z) [suma(z y, x)=0]

(z) [suma(z, pred(x))=0]

(z) [suma(y z, pred(x))=0]

Ninguna de las anteriores o mas de una

45.- Si la función f(x)=y[x pred(y)=0] el valor de f(5) es:

Ninguno de los anteriores

46.- La máquina de Turing R R SRL con la configuración juanjuan... se detiene con:

juanjuan

juanuan

Ninguna de las anteriores

47.- La función f(x,y) definida por minimalización como z[x y=0] es:

x+y-z

48.- La función (x) definida como:

0 si x=0

(x)=

si x 0

Es la función de Ackerman

No se puede expresar mediante combinaciones de recursivas primitivas

No es recursiva primitiva

Ninguna de las anteriores

49.- El crecimiento de la función 4n con relación al del polinomio n1000

Es más rápido

Es inferior

Es igual

Es indeterminado

50.- La gramática G=({S,A,B,C,D,E,F},{a,b},S,P) en donde las reglas P={S:=DA|CB, A:=CS|DE|a, B:=DS|CF|b, E:=AA, F:=BB, C:=a, D:=b} Genera el lenguaje:

L={anbn | n"0}

L={bnan| n"0}

L={anbm| m+n=k; m,n"0}

Ninguno de los anteriores

51.- ¿Cuál es la cadena de caracteres que al lenguaje descrito por la gramática G=({S,M,N,P},{x,y},S,P) en donde P={S:=SS|MN, N:=SP, M:=x, N:=y, P:=y}?

yyyxxyxy

xxxxxyyy

xyxyxyxy

Ninguna de las anteriores

52.- La gramática G=({S,A,B}, {a,b}, S, P) en donde P={S:=aB|bA, A:=bAA|aS|a, B:=bS|aBB|b}

Describe un lenguaje con palabras que tienen igual número de `a' que de `b'

Describe un lenguaje con palabras que tienen más `a' que `b'

Describe un lenguaje con palabras que tienen más `b' que `a'

Ninguno de los anteriores

53.- Dada una maquina de Turing general M con Q estados y símbolos, la máquina M' equivalente que sólo realiza una operación en cada paso, tiene un número de estados igual a:

4 + 3 " |Q| + 2 " |Q| " ||

2 " |Q| " || + 4

2 " |Q| mas los estados D,I,D' e I'

Ninguna de las anteriores

54.- Una gramática tipo 0 describe:

Lenguajes regulares

Lenguajes dependientes del contexto

Lenguajes independientes del contexto

Lenguajes sin restricciones

55.- La máquina de Turing M=({,|,*,,},{|,*},,{q0,q1,q2,q3,q4,q5},q0,{q5},f)

	\|		*
Q0	Q0 R	Q3 R	Q0 L		Q0* L
Q1	Q2 P	Q4 R		Q1 L	Q1 L
Q2	Q1 P	Q3 L	Q2 \| R	Q2 R	Q2 R
Q3	Q1\| R	Q1 R	Q2 R	Q3 \| L	Q3 L
Q4	Q1\| L	Q5 P		Q4 L	Q4 \| R
Q5

Si parte de una configuración inicial (q0 n1 * n2 ) en la que n1 y n2 son números enteros representados por barras verticales (p.ej.: n1=6=||||||, n2=3=|||)

calcula el algoritmo de euclides

Ninguna de las respuestas es correcta

calcula la suma de dos números enteros no nulos

calcula la diferencia de dos números enteros no nulos

56.- Las gramáticas regulares con (A,B N) y (w
) tienen sus reglas de la forma siguiente, o bien:

Ninguna de las respuestas es correcta

no son lineales ni por la derecha ni por la izquierda

A::=wB|w ó A:=Bw|w

son de tipo 2

57.- La máquina de Turing: acepta:

a/a,R

b/b,R

/,L /,R

q2 q4

a/,R a/,L a/a,L

b/b.L

/,R /,R

q0 q1 q5 h

b/b,R b/b,L

/,L

q3 q6

a/a,R /,R

b/b,R

/,L

Ninguna de las respuestas es correcta

palabras capicúas

palabras que tienen igual número de `a' que de `b'

palabras que tienen mayor numero de `a' que de `b'

58.- Dada la máquina de Turing M con |Q| estados y || símbolos, las máquinas de Turing equivalentes M1 que no puede escribir y cambiar de estado simultáneamente, M2 que no puede escribir y mover la cabeza simultáneamente y M3 que no puede cambiar de estado y mover la cabeza simultáneamente, el número de estados de:

M2 es mayor que el de M3

Ninguna de las respuestas es correcta

M1 es menor que el de M2

M1 es igual al de M2

59.- La función de concatenar dos números u y v en cualquier base n está definida por:

concatn(u,v)=u n|v| + v en donde |v|=x [(v
)=0] , entonces concat6(13,44) es:

1344

122

2852

Ninguna de las anteriores

60.- El proceso de la cadena xxyxxy... en la siguiente Máquina de Turing nos lleva a una complejidad espacial de:

R L y

Ninguna de las anteriores

61.- (x2)Si la función f(x)=y[g(x,y)=0] el Programa while que la calcula es:

begin Y:=0; Z:=g(X,0); if Z=0 then while Z=0 do begin Y:=succ(Y); Z:=g(X,Y) end end

begin Y:=0; Z:=g(X,0); if Z 0 then while Z=0 do begin Y:=succ(Y); Z:=g(X,Y) end end

begin Y:=0; Z:=g(X,0); if Z 0 then while Z 0 do begin Y:=succ(Y); Z:=g(X,Y) end end

Ninguna de las anteriores

62.- El valor de la función f(3,3) definida por minimalización:

f(x,y)= z [mult(suma(succ(y),z),succ(x))=0]

es igual a 16

es igual a 0

es "

Ninguna de las anteriores

63.- La función f(x,y) definida por recursividad primitiva: f(0,y)=0

f(x+1,y)=mult(succ (f(x,y)), ¬ eq(succ(f(x,y),y))

es la función cociente de división entera

es la función potencial xy

es la función resto de división entera

Ninguna de las anteriores

64.- Dada la gramática con las reglas de producción:

{S::=sentencia-while|sentencia-de-asignación,

sentencia-while::=while cond do S,

sentencia-de-asignación::=var:=exp,

cond::=cond cond|rel,

rel::=exp pred exp,

exp::=exp + exp | var | const,

pred::= > | =,

var::=x | y | z,

const::=0|1|2|3|4|5|6|7|8|9}

cuál de las siguientes sentencias está generada por dicha gramática:

while x=y do while x=z y=z do x:=y+z+4

x:=7 y:=6 while x>y do x:=y

while x>y x=2 do x=x+4

Ninguna de las anteriores

65.- Dada la gramática G=({S,O,R},{,},S,{S::=A(,R); R::=A(O, ); O::=L( , )} en donde A(x,y) significa “x está encima de y” y L(x,y) significa que “x está a la izquierda de y”

la figura | L(G) y la figura L(G)

Ninguna L(G)

66.- La función f(x,y) definida por minimalización: f(x,y)=z[(x y)=0]

es siempre igual a 0

es igual a 0 si x"y e " en caso contrario

Ninguna de las anteriores

67.- La máquina de Turing

	1	B
Q1		Q21R
Q2	Q31R	Q3IR
Q3	Q4BP	hBP
Q4	Q1BR	Q1BP

Con una cinta de entrada B111...........1BB.... calcula la función G(x):

g(x)=x+mod((x 2),2)

Ninguna de las respuestas es correcta

g(x)=x+2 mod(x,2)

g(x)=x+1 mod((x 1),2)

68.- (x2)Calcular la función f(5,4) si está definida mediante recursividad primitiva a partir de las dos funciones:

f(x,0)=succ(x)

f(x,y+1)=(
° f)(x,y)

Ninguna de las anteriores

69.- Las funciones siguientes pueden ser o no Recursivas primitivas:

3x+y(7x+5y) es R.P y la 2x2y4+9xy5+3 no es R.P

3x+y(7x+5y) es R.P y la 2x2y4+9xy5+3 es R.P

3x+y(7x+5y) no es R.P y la 2x2y4+9xy5+3 no es R.P

3x+y(7x+5y) no es R.P y la 2x2y4+9xy5+3 es R.P

70.- El proceso de la cadena xxyxxy... de la siguiente máquina de Turing nos lleva a una complejidad temporal de:

x x

R L y

y y

Ninguna de las anteriores

71.- Las funciones -recursivas:

un subconjunto de las funciones iniciales

son un subconjunto de las funciones recursivas primitivas

no son un subconjunto de las funciones recursivas parciales

Ninguna de las anteriores

72.- La función f(x,y)=y sólo si =0 x=1 es:

z[suma(z,pred(x))=0]

z[suma(z y,x)=0]

z[suma (y x,pred(x))=0]

Ninguna de las anteriores

73.- (x2)Si la complejidad temporal de una máquina de Turing es n, la complejidad espacial del cálculo:

es independiente de la temporal

no será mayor que n+1

es mayor que n+1

ninguna de las anteriores

74.- Si la función f(x,y)=x/y sólo cuando x es múltiplo de y, y ge(x,y)=0 si x<y y ge(x,y)=1 en caso contrario, f(x,y) será:

z[div(x,y) - suma(mult(coc(x,z),z),resto (x,z)))=0]

z[¬ eq (mult(y,z),x)=0]

z[mult(y,ge(x,mult(signo(z),y)))=0]

Ninguna de las anteriores

75.- El coc(x,y)= la parte entera de x/y si y 0 y coc(x,y)=0 si y=0, es recursiva primitiva y viene dado por:

coc(0,y)=0

coc(x+1,y)=coc(x,y) + ¬ eq(x+1, coc(mult(x,y),y)+y)

coc(0,y)=0

coc(x+1,y)=coc(x,y)+eq(x+1, mult(coc(x,y),y)+y)

coc(0,y)=0

coc(x+1,y)=coc(x,y)+ ¬ eq(x+1,mult(coc(x,y),y)+y)

Ninguna de las anteriores

76.- El lenguaje L={anb2n|n>0}

La gramática que lo define es de tipo 3

No es regular

La gramática que lo define es lineal por la izquierda

Ninguna de las anteriores

77.- La máquina de Turing

a,b

R } R

No acepta lenguajes de máquinas no deterministas

Es determinista

Acepta lenguajes de máquinas deterministas

Ninguna de las anteriores

78.- La máquina de Turing anterior reconoce el lenguaje formado por cadenas:

formadas por símbolos “a” y “b”

con dos o más símbolos iguales juntos

que acaben en “aa” o en “bb”

Ninguna de las anteriores

79.- La Gramática cuyas reglas de producción son P={E::=E + E | E " E | ( E ) | a | b}

Se pueden construir árboles de derivación distintos para una misma cadena

No es ambigua

Sus cadenas derivadas no son generadas por derivaciones distintas

Ninguna de las anteriores

80.- Las gramáticas cuyas reglas de producción son:

P={S::=aXbY, X::=aX|a; Y::=bY|b} y

R={S::=XXYY, X::=XX|a, Y::=YY|b}

son regulares

no son equivalentes

los lenguajes que describen son diferentes

Ninguna e las anteriores

81.- Cuál es la función que no está en O(n3)

ølog2nø

3n2+2n+1

5n3+2n2

82.- Si la correspondencia de símbolos es:

begin 000 end 001

X 010 0 011

:= 100 1 101

2 110 3 111

el programa número 1329 será:

begin X1:=0 end

beginX1:=1 end

begin X1:=2 end

begin X1:=3 end

83.- La máquina de Turing R R SRL si parte de la configuración ABC ABC ... llega a:

ABC C....

ABCC....

ABC BC....

Ninguna de las anteriores

84.- Dado ={a,b,c} y el lenguaje L={w/ 2<|w|"3} un contexto válido de b es:

(,)

(b,)

(,b)

(a,b)

85.- Dado el lenguaje L= {w/ 2<|w|"3} sobre el alfabeto ={a,b,c} existe una relación de equivalencia entre:

aa y bc

a y ab

b y ac

abc y ab

86.- La gramática G=({a,b,c},{S,A,B},S,P} en donde P={S::=AbA, A::=a, Ac::=AacA|AcB, B::=A|AB} es de tipo:

87.- La gramática G=({0,a},{S,A,B}, s, P) en donde P={S::=A, A::=0A|a, B::=aB|0} describe un lenguaje:

sin restricciones

dependiente del contexto

independiente del contexto

regular

88.- El número de estados de una máquina de Turing que no puede escribir y cambiar de estado simultáneamente es:

3 x |Q|

4 + 3 x |Q| + 2 x |Q| x ||

3x |Q| + 2 x |Q| x ||

Ninguna de las anteriores

89.- La máquina de Turing siguiente acepta la palabra:

¬ ¬ =

R } R L } L

abc

abcabc

abccba

Ninguna de las anteriores

90.- La máquina de Turing RC SLSL si parte con la configuración abcabc ... se detiene con la configuración:

ababc...

ab abc

91.- Si f viene definida por f(0)= ( ) y f(y+1)= ° ° f(y), f(3) será:

Ninguna de las anteriores

92.- Si el lenguaje L={ab} que palabra pertenece al lenguaje (L+)2:

ababab

aabb

aabbaabb

93.- Dada una gramática G con reglas de producción P={S::=AA, A::=AAA|a|bA|Ab} qué derivación se puede obtener de ella:

b2ababa

baba2ba

b2ab2ab2a

Ninguna de las anteriores

94.- (x2)La función definida por minimalización: F(x,y)= z (¬ eq (mult(y,z)=0) representa la función:

x/y si x es múltiplo de y

en caso contrario

x/y si y>0

en caso contrario

Ninguna de las anteriores

95.- Cual de las siguientes máquinas de Turing calcula la función F(w1,w2,w3)=w3

¬ B

DBSIDBDBSIISIISI

¬ B

DBDBISI

¬ B

DBSIDBSII

Ninguna de las anteriores o más de una

96.- (x3)Las funciones recursivas parciales:

No son todas computables por máquinas de Turing

No cumplen ninguna de las propiedades o cumplen más de una

Son computables por máquinas de Turing Deterministas

Son computables por máquinas de Turing No Deterministas pero no son computables por máquinas de Turing Deterministas

97.- Dada una máquina de Turing, siempre se cumple que:

La complejidad temporal siempre es superior a la longitud de la cadena

La complejidad espacial es mayor que la complejidad temporal mas 1

La complejidad espacial es menor o igual que la complejidad temporal mas 1

Ninguna de las anteriores o mas de una

98.- La función f(1,2, 3)=2 puede ser computada mediante la máquina de Turing

¬ B

DBDBSIIBIBSI

¬ B ¬ B

SI DBSI

¬ B ¬ B

DBDBSI IBSII

Ninguna de las anteriores o más de una

99.- La siguiente función definida por minimalización (z) [SUMA(GT(x, 3-z),z)=0] representa la función:

si x=0

f(x) =

" en caso contrario

si x=0

f(x) =

" en caso contrario

f(x) = " para todo x

Ninguna de las anteriores o más de una.

100.- Si f: se define mediante recursividad primitiva a partir de las funciones g= y h= ° ° p
entonces f es igual a:

SUMA ° (K
x p
)

MULT ° (K
x p
)

SUMA ° (K
x p
)

Ninguna de las anteriores o no es posible definir f de esa forma

101.- Si f: 3 se define mediante recursividad primitiva a partir de g=K
y H=mult(
,
)

xyz

x y z

Ninguna de las anteriores

102.- Dado el lenguaje L={, a, aa, ab, aaa, aab, aba, abb, ...} y la palabra w=bbb:

Ninguna de las respuestas es correcta

(a,b) no es un contexto válido de w en L y (ab, ) es un prefijo válido

(a,b) es un contexto válido de w en L y (, a) es un sufijo válido

(a,b) es un contexto válido de w en L y (, ab) es un sufijo válido

103.- Dada la Gramática con reglas de producción P={S::=AB, A::=aA|a, B::=Bb|B} la cadena aabbb:

tiene distintos árboles de derivación y no es una sentencia ambigua

tiene distintos árboles de derivación y es una sentencia ambigua

cada derivación se corresponde con un árbol diferente

104.- La gramática G=({a,b},{S,A},S,{S::=Ba|a, a::=Aaa|b| }) genera el lenguaje:

L={b(a2)*(b )

L={b a2nb / n }

L={b a2n b/ n }

Ninguna de las anteriores

105.- La Gramática G=({a,b},{S,A,A1,B,U,Z},X,P) en donde: P={S::=AA1|UB|a|ZA|AZ, Z::=AA1|UB|a|ZA|AZ, A::=b|AA1|UB|a|ZA|AZ, A1::=ZA, U::=a, B::=b}:

está en la forma normal de Chomsky

está en la forma normal de Greibach

tiene reglas unitarias

Ninguna de las anteriores

106.- Dadas las Gramáticas G1 con reglas de producción P1={X::=1XYZ|12Z, ZY::=YZ, 2Y::=22, 2Z::=2}, y G2 con reglas P2={S::=Aas|A, a::=sBa|ss|BA}:

Ninguna de las respuestas es correcta

G1 es estructurada por frases y G2 no es una gramática compresora

G1 es estructurada por frases y G2 es una gramática compresora

G1 no es estructurada por frases y G2 es una gramática compresora

107.- Dada la gramática G, la palabra x T es una instrucción de G si:

x está formada por símbolos no terminales únicamente

una relación de Thue entre el axioma y la palabra x

x está formada por símoblos terminales y no terminales

Ninguna de las anteriores

108.- Dada una máquina de Turing con |Q| estados y alfabeto , las máquinas de Turing equivalentes con capacidad restringida M1 que no puede escribir y cambiar de estado simultáneamente, M2 que no puede escribir y mover la cabeza simultáneamente y M3 que no puede cambiar de estado y mover la cabeza simultáneamente, tienen un número de estados:

|Q1| > |Q2| > |Q3|

|Q1| < |Q2| > |Q3|

|Q1| < |Q2| " |Q3|

Ninguna de las anteriores

109.- Dadas las palabras u=XYZ y v=Z, si las concatenamos y formamos la palabra w=uv

Ninguna de las respuestas es correcta

X no es cabeza propia de w y no es cola propia de w

X no es cabeza propia de w y es cola propia de w

X es cabeza propia de w y es cola propia de w

110.- Dada la maquina de turing M con la función de transferencia

	a	b
p	p a D	q b I
q	q a D	p a I

y las de:

M1	a	b	M2	0	1	a	b
p	s a P	t b P	p			s 0 P	t 1 P
q	u a P	r a P	q			u 0 P	r 0 P
r	p a I	p b I	r	r a I	r b I	p a P	p b P
s	p a D	p b D	s	s a D	s b D	p a P	p b P
t	q a I	q b I	t	t a D	t b D	q a P	q b P
u	q a D	q b D	u	u a I	u b I	q a P	q b P

M1 es equivalente a M y M2 no lo es

M1 es equivalente a M y M2 también lo es

M1 no es equivalente a M y M2 sí lo es

M1 no es equivalente a M y M2 tampoco lo es

111.- La máquina de Turing R R R SRL aplicada a la descripción instantánea ( pABCABC ) termina con la descripción instantánea siguiente:

(A B C p C)

Ninguna de las respuestas es correcta

112.- Dada la máquina de Turing:

a,b,c

D D } SRDSLI I

si arranca con la siguiente cinta a b c a b c ... se llega a :

b c a b c ...

b a b c ...

Ninguna de las anteriores

113.- Dada la máquina de Turing S
¿qué efecto produce sobre la configuración: a a b b c c

a a b b c c

Ninguna de las respuestas es correcta

b b c c

a a b b c c

114.- Dada la máquina de Turing No Determinista con el estado final de aceptación f F cuál de las palabras siguientes acepta:

a,b,c/R a,b,c/R

a/R

p q

b/R a,b,c/R

c/R a/R

c/R b/R

s t

Ninguna de las respuestas es correcta

abacc

ababac

abacc

115.- Si L1 " L2 se cumple que:

determinar si w L1 no es más complejo que determinar si f(w) L2

si L1 está en P entonces L2 no está en P

si L2 está en NP entonces L1 no está en NP

Ninguna de las anteriores

116.- La máquina de Turing de 3 cintas y una única cabeza, cuya entrada consiste en dos números binarios de igual longitud, situados en las dos primeras cintas y cuya función de transición es:

(q0, )=(q0, , R) si (b,b,b)

(q0, )=(q1, , L) si = (b,b,b)

(q1,(0,0,b))=(q1,(0,0,0), L) (q2,(0,0,b))=(q2,(0,0,1), L)

(q1,(0,1,b))=(q1,(0,1,1), L) (q2,(0,1,b))=(q2,(0,1,0), L)

(q1,(1,0,b))=(q1,(1,0,1), L) (q2,(1,0,b))=(q2,(1,0,0), L)

(q1,(1,1,b))=(q2,(1,1,0), L) (q2,(1,1,b))=(q2,(1,1,1), L)

(q1, (b,b,b))=(q2,(b,b,b), P) (q2,(b,b,b))=(q3,(b,b,b), P)

suma los dos números y deja el resultado en la tercera cinta

resta los dos números y deja el resultado en la tercera cinta

ninguna de las respuestas es correcta

realiza la operación lógica AND de los dos números y deja el resultado en la tercera cinta

117.- Dada la máquina de Turing M que simula el comportamiento de otra máquina de Turing MK3 a 3 cintas, si pasa de la situación primera a la segunda ejecuta las transiciones:

f(p,b,a,)=(q,b,2,I) y f(q,b,a,)=(q,,2D)

Ninguna de las respuestas es correcta

f(p,b,a,)=(q,b,2,I) y f(q,b,a,)=(q,,3,P)

f(p,b,a,)=(q,b,2,I) y f(q,b,a,)=(q,,3,I)

118.- La función f(x,y)= z[¬ eq(mult(y,z),x)=0] es:

f(x,y)=x/y sólo si y>0

f(x,y)=x/y sólo si y=0 y=1

Ninguna de las respuestas es correcta

f(x,y)=x/y sólo si x=múltiplo de y

119.- Si la función f(x)= y[mod(y,10)=0] para todo y " x

f(x) devuelve el primer múltiplo de 10 mayor o igual que su argumento

f(x) devuelve el primer múltiplo de 10 menor o igual que su argumento

Ninguna de las respuestas es correcta

F(x) devuelve el primer múltiplo de 10 mayor que su argumento

120.- Si la función f: 3 está definida por medio de recursividad primitiva a partir de las funciones g=mult(x,y) y h=suma(suma(s,y),suma(u,v) la f(4,2,2) será:

Ninguna de las anteriores

121.- La función :

mx(x,y)=x si x>y

mx(x,y)=y si x"y

en donde x,y , y la función sign=0 si es negativa y sign=1 en caso contrario, viene dada por:

mx(x,y)=suma(mult(1(x,y),sign(2(x,y) 1(x,y),mult(2(x,y),sign(1(x,y)) - 2(x,y))))

mx(x,y)=suma(mult(1(x,y),sign(2(x,y) 1(x,y),mult(1(x,y),sign(2(x,y)) - 2(x,y))))

mx(x,y)=suma(mult(1(x,y),sign(2(x,y) 2(x,y),mult(2(x,y),sign(1(x,y)) - 2(x,y))))

Ninguna de las anteriores

122.- La función factorial n!:

no es Recursiva Primitiva

Ninguna de las respuestas es correcta

es una función parcial

es O(nk)

123.- La función f(n)=5n3+2n2+22n+6 es O(n3), puesto que está acotada superiormente por g para:

c=1 y n0 "0

c=2 y n0"1

c=6 y n0"0

Ninguna de las anteriores

124.- Las máquinas de Turing Deterministas deciden Lenguajes en Tiempo Polinómico si:

el lenguaje pertenece a la clase NP

la complejidad temporal es mayor que p(|w|)

la complejidad espacial no es mayor que p(|w|)

Ninguna de las anteriores

125.- La complejidad Espacial Media del Algoritmo con pi={1/3,2/3,3/4,1/3} y ci={22,10,32,10} es:

124/3

124/12

181/12

Ninguna de las anteriores

126.- La función ø log2n ø:

no es O(n3)

no es O(n3) y si lo es O(n2)

no es O(n3) y no es O(n2)

Ninguna de las anteriores

b 1

b a

b 1

Tal vez te pueda interesar:

Descargar

Enviado por:	M.g.b.
Idioma:	castellano
País:	España

Palabras clave:

Reglas de Producción Máquina de Turing Recursividad Funciones Recursivas Determinista No determinista Complejidad Espacial

Te va a interesar