Teoría de autómatas | conjunto 10

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

Ques-1: Considere las siguientes declaraciones:

• X: Para cualquier lengua, una lengua L o su complemento L’ deben ser finitos.
• Y: DFA para lenguaje que contiene épsilon debe tener estado inicial como estado final.
• Z: Los autómatas finitos no deterministas son más poderosos que los autómatas finitos deterministas.

¿Cuál(es) de las siguientes afirmaciones es(n) correcta(s)?

(A) solo X
(B) solo Y
(C) solo Z
(D) todas las anteriores.

Explicación:
X: Es incorrecto. ya que, una lengua L y su complemento pueden ser infinitos.
Y: Es correcto, ya que si el idioma contiene épsilon, su estado inicial también debe ser final; de lo contrario, el DFA no podrá aceptar épsilon.
Z: Es incorrecto. ya que todos los idiomas aceptados por NFA también son aceptados por algunos DFA. Por lo tanto, NFA y DFA son equivalentes en potencia.

La opción (B) es verdadera.

Pregunta 2: ¿Cuál de las siguientes expresiones regulares describe el idioma sobre {a, b} que no consta de ningún par de b consecutivas?

(A) (a*baa*)(b + épsilon)
(B) (a + ba)*(b + épsilon)
(C) (a*baa*)*(b + épsilon) + a*
(D) ( a*ba*)*(b + épsilon) + a*(b + épsilon)

Explicación:

• (A) Es incorrecto. ya que, no contiene (a o epsilon).
• (B) Es correcto. ya que contiene (epsilon, a, b, ba, ab, …..), es decir, ningún par de b consecutivas.
• (C) Es incorrecto. ya que no contiene ‘ab’ o ‘aab’.
• (D) Es incorrecto. ya que contiene ‘bb’, lo cual no está permitido.

La opción (B) es verdadera.

Ques-3: ¿Cuál es la longitud de la string más corta que no está en el idioma sobre el alfabeto {0, 1} para la expresión regular que se muestra a continuación:

1*(0 + 1)*1* 

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

Explicación:
compruebe cada string generada sobre el alfabeto {0, 1} hasta llegar a la string más corta que no genera la expresión regular dada.
En este caso, la string más pequeña que no genera la expresión regular dada es 0110, cuya longitud es cuatro.

entonces, la opción (D) es verdadera.

Ques-4: Sea ‘X’ el conjunto de todos los idiomas aceptados por los autómatas deterministas push down (DPDA) por el estado final y ‘Y’ el conjunto de todos los idiomas aceptados por DPDA por la pila vacía, entonces, ¿cuál de las siguientes es verdadera?

(A) X es un subconjunto propio de Y
(B) X = Y
(C) X es un superconjunto propio de Y
(D) ninguna de las anteriores

Explicación:
el conjunto de idiomas aceptados por DPDA por estado final es un superconjunto adecuado de idiomas aceptados por DPDA de pila vacía. Entonces X es el superconjunto adecuado de Y.

La opción (C) es verdadera.

Pregunta-5: Considere que X e Y son dos idiomas sobre el alfabeto {0, 1} representado por la expresión regular 0*(10*)* y (0* + 1*)* respectivamente. ¿cual de los siguientes es verdadero?

(A) X es un subconjunto propio de Y
(B) Y es un subconjunto propio de X
(C) X = Y
(D) ninguno

Explicación:
Aquí,

L(X) 
= 0*(10*)* 
= {epsilon, 0, 1, 10, 01, 00, 11, ......} 

Y.

L(Y) 
= (0* + 1*)* 
= {epsilon, 0, 1, 10, 01, 00, 11, ....} 

Por lo tanto, ambos idiomas son equivalentes entre sí.

La opción (C) es verdadera.