PUERTA | PUERTA CS 2008 | Pregunta 8 – Part 1

¿Cuál de los siguientes es cierto para el idioma

(A) No es aceptado por una máquina de Turing
(B) Es regular pero no libre de contexto
(C) Es libre de contexto pero no regular
(D) No es ni regular ni libre de contexto, pero aceptado por Turing máquina

Respuesta: (D)
Explicación: La máquina de Turing se puede diseñar para una ^p utilizando el concepto de ‘tamiz de Eratóstenes’.

 
Supongamos que nos dan un número entero ‘n’ y queremos encontrar todos los números primos menores o iguales que ‘n’.

Repetimos los siguientes pasos:
encontramos el número más pequeño de la lista, lo declaramos primo y eliminamos todos los múltiplos de ese número de la lista. Seguimos haciendo esto hasta que cada elemento haya sido declarado primo o eliminado de la lista.

 

Ahora, si p = 0 o p = 1, rechazamos la entrada.
De lo contrario, reemplazamos la primera y la última ‘a’ con el símbolo $.

 

En los pasos anteriores, lo que hacemos es encontrar el primer símbolo que no sea negro de la izquierda. Deje que este símbolo ocurra en la posición ‘x’. Supongamos que ‘x’ es un número primo.
Si este símbolo que no está en blanco es $, se aceptará la string de entrada.
Pero, si el símbolo es ‘a’, lo marcamos como a* y reemplazamos todos los múltiplos de ‘x’ con el símbolo ‘en blanco’.
Si al final, el símbolo $se reemplaza con ‘en blanco’, rechazamos la string de entrada (porque p será múltiplo de alguna ‘x’ en ese caso).
De lo contrario, volvemos atrás y repetimos los pasos.

 
Por lo tanto, la entrada no es regular ni libre de contexto, pero es aceptada por una máquina de Turing.

 
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Cuestionario de esta pregunta