PUERTA | PUERTA-CS-2004 | Pregunta 89

L1 es un lenguaje recursivamente enumerable sobre Σ. Un algoritmo A efectivamente enumera sus palabras como w1, w2, w3, … Defina otro lenguaje L2 sobre Σ Union {#} como {wi # wj : wi, wj ∈ L1, i < j}. Aquí # es un nuevo símbolo. Considere las siguientes afirmaciones.

S1 :  L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive 

Cuál de las siguientes afirmaciones es verdadera ?
(A) Tanto S1 como S2 son verdaderos
(B) S1 es verdadero pero S2 no es necesariamente verdadero
(C) S2 es verdadero pero S1 no es necesariamente verdadero
(D) Ninguno es necesariamente verdadero

Respuesta: (A)
Explicación: S1 es VERDADERO .

Si L1 es recursivo, L2 también debe ser recursivo. Porque para comprobar si una palabra w=wi#wj pertenece a L2, podemos dar wi y wj al decisor de L1 y si ambos son aceptados entonces w pertenece a L1 y no de otro modo.

S2 es VERDADERO.

Con un decisor para L2 podemos hacer un decisor para L1 de la siguiente manera. Sea w1 la primera string enumerada por el algoritmo A para L1. Ahora, para comprobar si una palabra w pertenece a L1, crea una string w′=w1#w y dásela al decisor de L2 y, si se acepta, entonces w pertenece a L1 y no de otro modo.

Entonces, la respuesta debe ser (A). 
Cuestionario de esta pregunta