PUERTA | PUERTA-CS-2007 | Pregunta 30

El lenguaje L= {0 ⁱ 21 ⁱ | i≥0 } sobre el alfabeto {0,1, 2} es:
(A) no recursivo
(B) es recursivo y es un CFL determinista.
(C) es un lenguaje regular.
(D) no es una CFL determinista sino una CFL.

Respuesta: (B)
Explicación: Primero  diseñemos un autómata pushdown determinista para el lenguaje dado.

• Por cada aparición de ‘0’, EMPUJAMOS X en la pila.
• Cuando aparece ‘2’, no se realiza ninguna operación de pila. Pero, el estado de los autómatas cambia.
• Por cada aparición de ‘1’, extraemos X de la pila.
• Si al final Z ₀ está en la parte superior de la pila, se acepta la string de entrada

También diseñamos una máquina de Turing para el idioma dado.

• Cuando aparece ‘0’ en la string de entrada, lo reemplazamos con X. Luego, viaja a la esquina más a la derecha y reemplaza ‘1’ con Y.
• Volvemos al ‘0’ más a la izquierda y repetimos el proceso anterior.
• Mientras se desplaza hacia la derecha desde el principio de la string de entrada, si después de X aparece ‘2’ y después de ‘2’ aparece Y, entonces alcanzamos el estado HALT.

  Por lo tanto, el lenguaje dado es recursivo. Todo lenguaje recursivo es un CFL.
  Por lo tanto, la opción (B) es la respuesta.

  Comente a continuación si encuentra algo incorrecto en la publicación anterior.

Cuestionario de esta pregunta