CGU-NET | UGC NET CS 2016 Agosto – III | Pregunta 24

Considere las siguientes identidades para expresiones regulares:
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s )*
¿Cuáles de las identidades anteriores son verdaderas?
(A) (a) y (b) solamente
(B) (b) y (c) solamente
(C) (c) y (a) solamente
(D) (a), (b) y (c)

Respuesta: ( D)
Explicación:

• (r + s)* generará cualquier string que contenga r o s o ambos. Podemos dibujar DFA para (r + s)* y es lo mismo que (s + r)*. Es una expresión regular.
• (r*)* generará cualquier string que contenga r y su DFA se puede dibujar fácilmente y es igual que r*. También es una expresión regular.
• (r* s*)* generará cualquier string que contenga r o s o ambos. Podemos dibujar DFA para (r* s*)* y es lo mismo que (r + s)*. Es una expresión regular. Todas las opciones son verdaderas.

Entonces, la opción (D) es correcta.
Cuestionario de esta pregunta