The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 votes

Which of the following is TRUE?

- Every subset of a regular set is regular
- Every finite subset of a non-regular set is regular
- The union of two non-regular sets is not regular
- Infinite union of finite sets is regular

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

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

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 a^{n}b^{n} and another one is a^{n}b^{n}^{+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.

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={a^{n}b^{n }|m,n≥1} and

L2={a^{n}b^{n}^{+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.

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.

+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, a^{n} b^{n} for all n≥0 is non-regular as well as a^{n} b^{m} 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 {a^{n}b^{n }for n>0} which is not regular.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,531 answers

146,041 comments

62,298 users