proof regarding infinite union/intesection

Question

Q1:Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices).

Ans1: Consider the sets {0}, {01}, {0011}, etc. Each one is regular because it only contains one string. But the infinite union is the set {0ⁱ1ⁱ | i>=0} which we know is not regular. So the infinite union cannot be closed for regular languages.

Q2: What about infinite intersection?

Ans2: We know that

{0ⁱ1ⁱ | i>=0} = {0} U {01} U {0011} U ...,

Taking complements and applying DeMorgan's law gives us

{0ⁱ1ⁱ | i>=0}^c = {0}^c ^ {01}^c ^ {0011}^c ^ ...,

Where we are using U to deonte union and ^ to denote intersection. Recall the complement of a regular language is regular, and hence the complement of a not-regular language is not regular. So we can conclude that the left hand side of the equation is not-regular, and each term in the intersection is regular. Therefore infinite intersection does not preserve regularity.

Please explain what is infinite union/ infinite intersection and also explain the answer

This question is from aduni.org

Comments

omg, this came in GATE 2020 this year

---

Source of question has some useful proofs:

http://www.aduni.org/courses/theory/courseware/psets/Problem_Set_01_Solutions.html

---

{0i1i | i>=0} = {0} U {01} U {0011} U ...,

Is this equal I think {0} shouldn't be in the equation?

Answer 1

Infinite union means we do union operation infinite (uncountably many) times, same with infinite intersection.

Answer 2

In your example u can draw dfa for finite string but u can't draw for a^i b^i where i >0, the same applies to the intersection