PUERTA | PUERTA-CS-2007 | Pregunta 7 – Part 3

¿Cual de los siguientes es verdadero?
(A) Todo subconjunto de un conjunto regular es regular.
(B) Todo subconjunto finito de un conjunto no regular es regular.
(C) La unión de dos conjuntos no regulares no es regular.
(D) La unión infinita de conjuntos finitos es regular.

Respuesta: (B)
Explicación: Algunos puntos para conjuntos regulares:

• Un conjunto es siempre regular si es finito.
• Un conjunto siempre es regular si se puede dibujar un DFA/NFA para él.

Opción A: Todo subconjunto de un conjunto regular es regular es Falso.
Para los alfabetos de entrada a y b, a*b* es normal. Se puede dibujar un DFA para a*b* pero anbn para n≥0, que es un subconjunto de a*b*, no es regular ya que no podemos definir un DFA para él.

Opción B: Todo subconjunto finito de un conjunto no regular es regular es Verdadero.
Todos y cada uno de los conjuntos que son finitos pueden tener un DFA bien definido, por lo que, ya sea un subconjunto de un conjunto regular o un conjunto no regular, siempre es regular.

Opción C: La unión de dos conjuntos no regulares no es regular es Falsa.
Para los alfabetos de entrada a y b, a ⁿ b ⁿ para todo n≥0 no es regular, así como a ⁿ b ^mpues n≠m tampoco es regular pero su unión es a*b* que es regular.

Opción D: La unión infinita de conjuntos finitos es regular es Falsa.
Para los alfabetos de entrada a y b los conjuntos {ab}, {aabb}, {aaabbb}…….. son regulares pero su unión {ab} U {aabb} U {aaabbb} U …………………….. da {anbn para n>0} que no es regular.

Esta solución es aportada por Yashika Arora .

Cuestionario de esta pregunta