GATE CSE 2007 | Question: 7

Question

Which of the following is TRUE?

• A. Every subset of a regular set is regular
• B. Every finite subset of a non-regular set is regular
• C. The union of two non-regular sets is not regular
• D. Infinite union of finite sets is regular

Answer 1

Correct Option: B

Every finite subset of a non-regular set is regular.

Any finite set is always regular. 

$\Sigma^*$ being regular any non regular language is a subset of this, and hence (A) is false.

If we take a CFL which is not regular, and takes union with its complement (complement of a CFL which is not regular won't be regular as regular is closed under complement), we get $\Sigma^*$ which is regular. So, (C) is false. 

Regular set is not closed under infinite union. Example:
Let $L_i = \{0^i1^i \}, i \in N$

Now, if we take infinite union over all $i$, we get

$L =\{0^i1^i \mid i \in N\}$, which is not regular. 

So, (D) is false. 

Comments

how so ?

how union of two non regular languages  given above, is regular !!

---

@akash_chauhan why do you think the union is not regular?

---

---- 2 days back, I thought of  n as constant in L2.

     and, thereby thinking sol.  for n! = m^n  ( treating “n” as constant )

BUT<>  now, it’s OK 

         → UNION will be regular.

Answer 2

If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a non-regular set is regular.
Every subset of regular set is regular, is false. For example L = {$a^{n} b^{n}$ | n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two non-regular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {$a^{n} b^{n}$| n ≥ 0} and its complement Lc = {$a^{m} b^{n}$ | m ≠ n } U b*a*.
If we take UNION of L and $L^{c}$ , we will get ∑*, which is regular. Hence the UNION of two non-regular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.

Comments

@King Suleiman @GateCse @Kabir5454 @Abhrajyoti00

If we take UNION of L and L^c , we will get ∑*, which is regular. Hence the UNION of two non-regular set may or may not be regular.

Any example where union of two non-regular not being regular.

 

---

@GateOverflow04 Here you go, an eg of two non-reg lang being non-reg:- 

L1 = $a^nb^n$ [CFL, not regular]

L2 = $c^nd^n$ [CFL, not regular]

L1 U L2 =  $a^nb^n$ U $c^md^m$ [CFL, not regular]

Answer 3

Some points for Regular Sets:

• A set is always regular if it is finite.
• A set is always regular if a DFA/NFA can be drawn for it.

Option A: Every subset of a regular set is regular is False.
For input alphabets a and b, a*b* is regular. A DFA can be drawn for a*b* but a$^n$ b$^n$  for n≥0 which is a subset of a*b* is not regular as we cannot define a DFA for it.

Option B: Every finite subset of a non-regular set is regular is True.
Each and every set which is finite can have a well-defined DFA for it so whether it is a subset of a regular set or non-regular set it is always regular.

Option C: The union of two non-regular sets is not regular is False.
For input alphabets a and b, a$^n$ b$^n$ for all n≥0 is non-regular as well as a$^n$ b$^m$ for n≠m is also non- regular but their union is a*b* which is regular.

Option D: Infinite union of finite sets is regular is False.
For input alphabets a and b sets {ab}, {aabb}, {aaabbb}…….. are regular but their union {ab} U {aabb} U {aaabbb} U …………………….. gives {a$^n$ b$^n$ for n>0} which is not regular.

Courtesy:GeeksForGeeks