Which of the following is TRUE?a)Every subset of a regular set is regularb)Every finite subset of a non-regular set is regularc)The union of two non-regular sets is not regulard)Infinite union of finite sets is regularCorrect answer is option 'B'. Can you explain this answer?

Question

Answer

(B) Every finite subset of a non-regular set is regular.
Any finite set is always regular.

∑* 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 ∑* which is regular. So, (C) is false.

Regular set is not closed under infinite union. Example: Let Li = {0i1i }, i ∊ N

Now, if we take infinite union over all i, we get

L = {0ⁱ1ⁱ | i ∊ N}, which is not regular. So, D is false.

Answer

(B) Every finite subset of a non-regular set is regular.
Any finite set is always regular.

∑* 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 ∑* which is regular. So, (C) is false.

Regular set is not closed under infinite union. Example: Let Li = {0i1i }, i ∊ N

Now, if we take infinite union over all i, we get

L = {0ⁱ1ⁱ | i ∊ N}, which is not regular. So, D is false.

Answer

Explanation:

To determine which statement is true, we need to understand the definitions of regular sets and non-regular sets.

Regular Sets:
A regular set is a set of strings that can be recognized by a finite automaton. In other words, a regular set can be described by a regular expression or generated by a regular grammar.

Non-regular Sets:
A non-regular set is a set of strings that cannot be recognized by a finite automaton. Non-regular sets are also known as context-free or context-sensitive languages.

Now let's analyze each statement to determine which one is true.

a) Every subset of a regular set is regular:
This statement is not true. While it is true that every regular set is a subset of a larger regular set, not every subset of a regular set is regular. Consider the regular set of all strings containing only the letter 'a'. The subset of this regular set containing strings with an odd number of 'a's is not regular.

b) Every finite subset of a non-regular set is regular:
This statement is true. A non-regular set contains strings that cannot be recognized by a finite automaton. However, if we take a finite subset of this non-regular set, the number of strings in the subset is finite. A finite set can always be recognized by a finite automaton, so every finite subset of a non-regular set is regular.

c) The union of two non-regular sets is not regular:
This statement is not true. The union of two non-regular sets can be regular. For example, consider two non-regular sets: one containing all strings of the form 'a^n b^n' and the other containing all strings of the form 'a^n c^n'. The union of these two sets is the set of all strings of the form 'a^n b^n' or 'a^n c^n', which is a regular set.

d) Infinite union of finite sets is regular:
This statement is not true. An infinite union of finite sets can be regular, but it can also be non-regular. It depends on the specific sets being unionized. For example, the infinite union of the sets {a}, {aa}, {aaa}, ... is the set of all strings consisting of one or more 'a's, which is a regular set. However, the infinite union of the sets {a}, {ab}, {abc}, ... is the set of all strings consisting of one or more 'a's followed by one or more 'b's followed by one or more 'c's, which is not a regular set.

Therefore, the correct answer is option B: Every finite subset of a non-regular set is regular.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2026 Mock Test Series

Crash Course for GATE CSE

Computer Networks

Question Bank for GATE Computer Science Engineering

Crash Course: Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company