Teoría de autómatas | conjunto 7

Estas preguntas tienen fines prácticos para el examen GATE CS.

Pregunta-1: Considere L= {(TM) | TM es la máquina de Turing que se detiene en todas las entradas y L(TM)= L’ para algún lenguaje indecidible L’}. Aquí, (TM) es la codificación de una máquina de Turing como una string sobre el alfabeto {0, 1}, luego L es:

(A) decidible y recursivamente enumerable
(B) decidible y recursiva
(C) decidible y no recursiva
(D) indecidible y recursivamente enumerable

Explicación:
Aquí, TM es una máquina de Turing que se detiene en todas las entradas, por lo que L(TM) es decidible y usted sabe que detener la máquina de Turing acepta lenguaje recursivo y el complemento del lenguaje recursivo puede enumerarse recursivamente, lo cual es indecidible.

Por lo tanto, L es decidible y recursivo. La opción (B) es correcta.

Pregunta-2: ¿Cuál(es) de los siguientes problemas es(n) decidible(s)?

(A) dadas dos gramáticas sensibles al contexto P y Q, ¿es L(P)= L(Q)?
(B) dada una gramática sensible al contexto P, ¿L(P) es finito o no?
(C) dada una gramática libre de contexto P, ¿L(P) es finita o no?
(D) dadas dos gramáticas libres de contexto deterministas P y Q, ¿es L(P)= L(Q)?

Explicación:
Ya que sabes que para el problema de finitud del lenguaje libre de contexto es decidible.

Entonces, la opción (C) es correcta.

Pregunta-3: ¿Cuál de las siguientes afirmaciones es verdadera?

(A) dada una gramática recursivamente enumerable P, L(P) es un lenguaje regular.
(B) dadas dos gramáticas libres de contexto P y Q, L(P)= L(Q).
(C) dadas dos gramáticas libres de contexto deterministas P y Q, L(P) es un subconjunto de L(Q).
(D) dada una gramática sensible al contexto P, el complemento de L(P) es lo mismo que L(P).

Explicación:
ya que sabe que para un complemento de idioma sensible al contexto de un idioma determinado es un idioma del mismo tipo.

Entonces, la opción (D) es correcta.

Pregunta-4: Considere L= {(a ^p )* | P es un número primo} sobre el alfabeto {a}, entonces, ¿cuál es el número mínimo de estados en NFA que acepta el lenguaje L?

(A) tres
(B) cinco
(C) dos
(D) cuatro

Explicación:

L = {(ap)* | P is a prime number}
L = (a2)* U (a3)* U (a5)* U ......
L = {epsilon, a2, a3, a4, a5, ......}  

Es decir, todas las strings de a excepto ‘a’

In the above NFA, only string ‘a’ is not accepted. Hence, number of states required is three.

Entonces, la opción (A) es correcta.

Ques-5: Considere las gramáticas libres de contexto sobre el alfabeto {a, b} dado a continuación, donde ‘S’ no es terminal

X:S= aSa |aSb |epsilon
Y:S= aaS |bbS |epsilon 

¿Cuál es la longitud de la string más corta que no pertenece a L(X) pero pertenece a L(Y)?

(A) tres
(B) cuatro
(C) uno
(D) seis

Explicación:
Aquí, L(X)= conjunto de palíndromos pares y L(Y)= (aa + bb)*
Entonces, la string “aabb” o “bbaa” pertenece a L(Y) pero no pertenece a L(X) . Por lo tanto, cuatro es la respuesta.

La opción (B) es verdadera.