Teoría de autómatas | conjunto 8

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

Ques-1: ¿Cuál de los siguientes idiomas es regular?

(A) {ancho x ancho ^R | w,x ∈ (a+b)+}
(B) {wxw ^R | w ∈ (a+b)*, x ∈ {a,b}}
(C) {ww ^R x | w,x ∈ (a+b)+}
(D) {ww ^R | w ∈ (a+b)*}

Explicación:

• (A) Es correcto, ya que este lenguaje puede formar expresiones regulares que son {{ a(a + b) ⁺ a } + {b(a + b) ⁺ b}}, es decir, comienzan y terminan con el mismo símbolo.
• (B) Es un lenguaje libre de contexto determinista ya que, la string antes y después de ‘x’ son iguales, por lo que coincide.
• (C) No puede ser regular ya que ww ^R se realiza al principio, lo que requiere una comparación que no se puede realizar a través de autómatas finitos.
• (D) Tampoco es regular ya que se requiere comparación.

La opción (A) es verdadera.

Pregunta-2: Sea w cualquier string de longitud n en {a, b}*. Considere que ‘L’ es el conjunto de todas las strings que terminan con al menos n a. ¿Cuál es el número mínimo de estados en autómatas finitos no deterministas que aceptan ‘L’?

(A) (n+3)
(B) (n+1)
(C) norte
(D) 2 ^norte

Explicación:
es correcto ya que el número mínimo de estados requeridos para que NFA termine con al menos 2 a es (2 + 1), es decir, la expresión regular será (a + b)*aa

Por lo tanto, el número de estados requeridos para al menos n a será (n+1).

La opción (B) es verdadera.

Pregunta 3: ¿Cuál es el número mínimo de estados en autómatas finitos deterministas (DFA) para strings que comienzan con ba ² y terminan con ‘a’ sobre el alfabeto {a, b}?

(A) Diez
(B) Nueve
(C) Ocho
(D) Seis

Explicación:

En el DFA anterior, el número mínimo de estados requeridos es seis.

La opción (D) es correcta.

Ques-4: Considere las siguientes declaraciones:

S1 = {(an)m | n = 0}
S2 = {anbn | n>=1} U {anbm | n>=1, m>=1} 

¿Cuál de los siguientes es regular?

(A) solo S1
(B) solo S2
(C) tanto S1 como S2
(D) ninguno

Explicación:
Ambos idiomas dados son regulares. La opción (C) es correcta.

Ques-5: ¿Cuál es el número de estados en NFA mínimo (autómatas finitos no deterministas), que acepta un conjunto de todas las strings en las que el penúltimo símbolo es ‘a’ sobre el alfabeto {a, b}?

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

Explicación:

En la NFA anterior, el número mínimo de estados requeridos es cuatro.

La opción (B) es verdadera.