CGU-NET | UGC NET CS 2016 Julio – III | Pregunta 57

Dada una Máquina de Turing
M = ({q ₀ , q ₁ , q ₂ , q ₃ }, {a, b}, {a, b, B}, δ, B, {q ₃ })
Donde δ es una función de transición definida como
δ(q ₀ , a) = (q ₁ , a, R)
δ(q ₁ , b) = (q ₂ , b, R)
δ(q ₂ , a) = (q ₂ , a, R)
δ(q ₃ , b) = (q ₃ , b, R)
El lenguaje L(M) aceptado por la Máquina de Turing se da como:
(A) aa*b
(B) abab
(C) aba*b
(D) aba*

Respuesta: (C)
Explicación: Según la pregunta dada, tenemos la transición:
δ(q ₀ , a) = (q ₁ , a, R)
δ(q ₁ , b) = (q ₂ , b, R)
δ( q ₂ , a) = (q ₂ , a, R)
δ(q ₃ , b) = (q ₃ , b, R)
Podemos dibujar un DFA:

El lenguaje será aba*b.
Entonces, la opción (C) es correcta.
Cuestionario de esta pregunta