Teoría de autómatas | conjunto 9

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

Pregunta-1: Considere las siguientes dos afirmaciones con respecto a la Contabilidad: 
 

• Declaración-1: Si la unión X de ‘Y’ es incontable, entonces tanto el conjunto ‘X’ como el conjunto ‘Y’ deben ser incontables. 
   
• Declaración-2: El producto cartesiano de dos conjuntos contables ‘X’ e ‘Y’ es contable. 
   

¿Cuál de las siguientes opciones es verdadera? 

(A) solo la afirmación 1 
(B) solo la afirmación 2 
(C) ambas afirmaciones son verdaderas 
(D) ninguna 

Explicación: 
la declaración 1 no es correcta porque solo un conjunto puede ser incontable, pero no es necesario que sean ambos. 
La declaración 2 es correcta porque el producto cartesiano de dos conjuntos contables es contable. 

La opción (B) es verdadera. 

Ques-2: Considere las siguientes declaraciones: 
 

• X: Dada una gramática, comprobar si la gramática no es regular es un problema decidible. 
   
• Y: Si P es regular y Q no es regular entonces (PQ) es necesariamente no regular. 
   
• Z: El lema de bombeo se puede usar para probar que el lenguaje dado es regular. 
   

¿Cual de los siguientes es verdadero? 

(A) solo X 
(B) solo Y 
(C) tanto X como Z 
(D) tanto X como Y 

Explicación: 
X es un problema decidible porque puedes revisar la gramática regular con la ayuda de algunas producciones. Entonces, esta afirmación es correcta. 

Y no es correcto, por contraejemplo P= nulo y Q= {a ⁿ b ⁿ | n ≤ 0} entonces, PQ= nulo que es regular. 

Z tampoco es correcto porque Pumping lemma puede probar que el lenguaje no es regular pero no puede probar que el lenguaje es regular. 

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

Ques-3: Considere que X e Y son dos idiomas sensibles al contexto y ‘R’ es cualquier idioma normal. Entonces, ¿cuál de los siguientes es/son verdaderos? 

(A) La unión X de R es regular. 
(B) La intersección X de Y es sensible al contexto. 
(C) El complemento de Y es lenguaje sensible al contexto. 
(D) Ninguno. 

Explicación: 
 

• (A) Unión X de R = CSL Unión de R = CSL pero no regular. Por lo tanto es incorrecto. 
   
• (B) Intersección de dos lenguajes sensibles al contexto = CSL ya que los lenguajes sensibles al contexto están cerrados bajo la intersección. 
   
• (C) Complemento de CSL = CSL ya que los lenguajes sensibles al contexto están cerrados bajo complementario. 
   

Tanto la opción (B) como la (C) son correctas. 

Pregunta-4: Considere tres problemas de decisión X, Y y Z. Se sabe que X es decidible e Y es indecidible, entonces, ¿cuál es el siguiente? 

(A) Z es decidible si X es reducible a Z 
(B) Z es indecidible si Z es reducible a Y 
(C) Z es indecidible si Y es reducible a Z 
(D) Z es decidible si Z i es reducible al complemento de Y. 

Explicación: 
Supongamos que hay dos problemas, A y B. Si A es indecidible y reducible a B, entonces B también es indecidible y si B es decidible y reducible a A, entonces A también es decidible. 

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

Ques-5: ¿Cuál de los siguientes es decidible? 

(A) Una máquina de Turing imprime una letra específica. 
(B) Una máquina de Turing calcula el producto de dos números. 
(C) Una máquina de Turing arbitraria se detiene después de cincuenta pasos. 
(D) ninguna de las anteriores. 

Explicación: 
La opción (B) es correcta ya que la máquina de Turing puede calcular cualquier operación matemática. 
La opción (C) también es correcta ya que se da un número de pasos para que sea decidible. 

Tanto la opción (B) como la (C) son correctas.