The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

+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

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 a^{n}b^{n} and another one is a^{n}b^{n}^{+1} then how is their union is a regular language?

+2

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.

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

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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,913 questions

52,293 answers

182,250 comments

67,739 users