Considere la expresión regular R = (a + b)* (aa + bb) (a + b)*<br>
¿Cuál de las expresiones regulares dadas a continuación define el mismo lenguaje definido por la expresión regular R?
(A) (a(ba)* + b(ab)*)(a + b) +
(B) (a(ba)* + b(ab)*)*(a + b)*
(C) (a (ba)* (a + bb) + b(ab)*(b + aa))(a + b)*
(D) (a(ba)* (a + bb) + b(ab)*(b + aa))(a + b) +
Respuesta: (C)
Explicación: <!–A acepta ab pero dado no
B vacío puede aceptarse, no dado –>
El DFA anterior se puede simplificar resolviendo el bucle en los estados B y C y eliminando las transiciones adicionales en los estados finales, que es el siguiente:
Para llegar a un estado final desde B, podemos tener el alfabeto ‘a’ para pasar al estado D o ‘bb’ para pasar al estado E.
De manera similar, para llegar a un estado final desde C, podemos tener el alfabeto ‘b’ para pasar al estado estado E o ‘aa’ para pasar al estado D.
Por lo tanto, la expresión regular es:
(a(ba)*(a+bb) + b(ab)*(b+ aa))(a+b)*
a(ba)*(a+bb): pasar de A a B y B a cualquiera de los estados finales
b(ab)*(b+ aa): pasar de A a C y C a cualquiera de los estados finales estados
Nota: También podemos usar el método de eliminación de opciones para tales preguntas, es decir, podemos rechazar una opción si
encuentre al menos una string que no valide la expresión regular.
La opción (A) acepta ab pero la expresión regular dada no lo hace.
La opción (B) acepta una string vacía pero la expresión regular dada no lo hace.
La opción (D) no acepta aa pero la expresión regular dada sí.
Esta solución es aportada por Yashika Arora
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA