2.2k views

Which of the following is TRUE?

1. Every subset of a regular set is regular
2. Every finite subset of a non-regular set is regular
3. The union of two non-regular sets is not regular
4. Infinite union of finite sets is regular
retagged | 2.2k views

(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.

edited by
0
I have a doubt in this . How can you say $\Sigma^*$ is regular ? is that an infinite set? and my understanding is infinite sets cannot be regular unless it is representable by a regular expression?
+1
Take any DFA and mark all the states of that DFA as final
i.e. Q=F
Where, Q--> Set of all states
F---> Set of final states
So, when all the states are final states, then this DFA will accept "Σ∗"(i.e. every string made by the alphabets).
Therefore any Language which is accepted by DFA is also regular

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, an bn for all n≥0 is non-regular as well as an bm 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 {anbn for n>0} which is not regular.

edited
0

In option C: anbm is regular. i.e. a DFA  is possible for it.

Although we can write:

The union of two non-regular languages L1 = { anbm ∣ n<m } and

L2 = { anb∣ n>m } is a*b* which is a regular language...

0

anbm where n<=m

anbm where n>m

as 2 non-regular languages and

a*b* as regular language

should suit here as example for option C