3.1k 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 | 3.1k 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
+1
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
+1

I have question regarding option C.

I one non regular language is anbn and another one is anbn+1 then how is their union is a regular language?

+3
Because it is not always true.

Say,

$L_1 = \{a^mb^n|m=n\geq0\}$ and

$L_2 = \{a^mb^n|m\neq n\:and \:m,n\geq0\}$

Both $L_1$ and $L_2$ are not regular but

$L_1\cup L_2$ will be $a^*b^*$ which is regular.
0

Although the union of the two languages maybe regular in the example you stated.

But I have doubts that this may not always be the case. Please consider this example and help me to understand how their union is regular?

L1={anb|m,n≥1} and
L2={anbn+1|m,n≥1}

I may have missed some point but I want to know if their is a mistake from my side.

+2
The statement is saying union of two non regular languages has to be non regular, which is false.

If the statement would have been

Union of two non regular languages can be regular

or

Union of two non regular languages can be non regular

Then, it would have been true and we even gave examples for both. But, saying, Union of two non regular languages is not regular is false as it is not always the case.
0
I got the point. Thank You.
0
Pl show how l1 U l2 is a*b* ?

Pl explain
0

$L_1$ has all the strings where number of a's are equal to number of b's and a's are followed by b's

$L_2$ has all the strings where number of a's are not equal to number of b's and a's are followed by b's

Union will have all strings where a's are followed by b's.

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.

1
2