The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.3k 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.5k points)
retagged by | 2.3k views

2 Answers

+22 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
+15 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

38,112 questions
45,619 answers
132,311 comments
49,292 users