The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.4k 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
asked in Theory of Computation by Veteran (59.6k points)
retagged by | 2.4k views

2 Answers

+25 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
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
0

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?

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

+1
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.
+17 votes

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.

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



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

40,871 questions
47,531 answers
146,041 comments
62,298 users