Complejidad y Computabilidad

COMPLEJIDAD Y COMPUTABILIDAD

Cuestionario de Twitter

Test 1

1. Sea L = ε, entonces L es recursivo.

VERDADERO.

Efectivamente L = ε es recursivo. Por ejemplo, la MT dada por δ(q1,B) = (q2,B,L) lo decide.

1. Sea L = 1(0+1)*, entonces L es recursivo.

VERDADERO.

Efectivamente L = 1(0+1)* es recursivo. Por ejemplo, la MT dada por δ(q1,1) = (q2,1,R) lo decide.

1. Sea L = 0(0+1)*, entonces L es recursivo.

VERDADERO.

Efectivamente L = 0(0+1)* es recursivo. Por ejemplo, la MT dada por δ(q1,0) = (q2,0,R) lo decide.

1. Puede ocurrir que L sea recursivo y que no exista ninguna MT que decida el complementario de L.

FALSO.

Efectivamente, no puede ocurrir que L sea recursivo y que no exista ninguna MT que decida al complementario de L, ya que si L es recursivo, el complementario de L también es recursivo y esto equivale a que existe una MT que lo decide.

1. Los lenguajes recursivos son cerrados respecto de la operación complementario.

VERDADERO.

Efectivamente, los lenguajes recursivos son cerrados respecto de la operación complementario.

1. Un lenguaje es recursivo si y solo si existe una MT que lo acepta.

VERDADERO.

Efectivamente, un lenguaje es recursivo si y solo si existe una MT que lo decida.

Test 2

1. Sea wi = 1000, entonces Mi es la M1000.

FALSO.

Si wi = 1000, Mi no es válida y se le asocia la MT “vacía” (un estado y ninguna transición). De igual forma, M1000 está dada por la cadena 111101000 también no válida, por lo que se la asocia también la MT “vacía”.

1. Sea wi = 01000100100010, entonces L(Mi) verifica que L(Mi) = vacío.

FALSO.

Efectivamente, wi = 01000100100010 es un código válido, asociado a M20770, que verifica que L(Mi) = ε, distinto del vacío.

1. Sea wi = 01010010100, entonces L(Mi) verifica que L(Mi) = vacío.

FALSO.

Efectivamente, wi = 01010010100 es un código válido, asociado a M2708, que verifica que L(Mi) = 0(0+1)*, distinto del vacío.

1. Sea wi = 0101001010, entonces L(Mi) verifica que L(Mi) = vacío.

FALSO.

Efectivamente, wi = 0101001010 es un código válido, asociado a M1354, que verifica que L(Mi) = 0(0+1)*, distinto del vacío.

1. Sea wi = 01010011010, entonces L(Mi) verifica que L(Mi) = vacío.

VERDADERO.

Al ser wi = 01010011010 un código no válido, se le asocia L(Mi) vacío.

1. Las MT deterministas de una cinta pueden codificarse de forma que constituyan un conjunto infinito numerable.

VERDADERO.

Efectivamente, las MT deterministas de una cinta pueden codificarse de forma que constituyan un conjunto infinito numerable.

Test 3

1. Si wi pertenece a Lnd, entonces el vector característico de Mi está formado por todo unos.

FALSO.

Efectivamente, si wi pertenece a Lnd, entonces no se tiene forzosamente que todo el vector característico de Mi esté formado por unos.

1. Si el vector característico de Mi está formado por todo unos, entonces wi pertenece a Lnd.

VERDADERO.

Efectivamente, si el vector característico de Mi está formado por todo unos, entonces wi pertenece a Lnd.

1. Si wi pertenece a Ld, entonces el vector característico de Mi tiene un 1 en la coordenada n-ésima.

FALSO.

Efectivamente, si wi pertenece a Ld, entonces el vector característico de Mi tiene un 0 en la coordenada i-ésima.

1. L(M682) es un ejemplo de lenguaje de diagonalización.

FALSO.

L(M682) no es un ejemplo de lenguaje de diagonalización. Lo que sí es cierto es que w682 pertenece al Ld, ya que L(M682) es el conjunto vacío y w682 no pertenece, por tanto, a L(M682).

1. w2708 pertenece a Ld.

FALSO.

Efectivamente, w2708 pertenece a L(M2708) = 0(0+1)*, por lo que w2708 no pertenece a Ld.

...