retagged by
15,261 views

3 Answers

Best answer
60 votes
60 votes

Correct Option: 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. 

edited by
7 votes
7 votes
If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a non-regular set is regular.
Every subset of regular set is regular, is false. For example L = {$a^{n} b^{n}$ | n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two non-regular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {$a^{n} b^{n}$| n ≥ 0} and its complement Lc = {$a^{m} b^{n}$ | m ≠ n } U b*a*.
If we take UNION of L and $L^{c}$ , we will get ∑*, which is regular. Hence the UNION of two non-regular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
5 votes
5 votes

Some points for Regular Sets:

  • A set is always regular if it is finite.
  • A set is always regular if a DFA/NFA can be drawn for it.

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.

Courtesy:GeeksForGeeks

Answer:

Related questions

39 votes
39 votes
2 answers
1
Kathleen asked Sep 21, 2014
14,053 views
Which of the following languages is regular?$\left\{ww^R \mid w \in \{0, 1\}^+\right\}$$\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$$\left\{wxw^R \mid x, w \in \{0, 1\}...
21 votes
21 votes
7 answers
2
pC asked Dec 21, 2015
7,772 views
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...
27 votes
27 votes
4 answers
3
Kathleen asked Sep 21, 2014
13,758 views
Match the following:$$\begin{array}{llll} \text{(P)} & \text{SMTP} &(1)& \text{Application layer} \\ \text{(Q)} & \text{BGP}& (2) & \text{Transport layer} \\ \text{(R)}...