The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 votes

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
asked in Theory of Computation by Veteran (59.9k points)
retagged by | 2.8k views

1 Answer

+26 votes
Best answer

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

answered by Active (2.5k points)
edited by
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?
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

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?

Because it is not always true.


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

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

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

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


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.
I got the point. Thank You.
Pl show how l1 U l2 is a*b* ?

Pl explain


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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,913 questions
52,293 answers
67,739 users