Which of the following is TRUE?a)Every subset of a regular set is regu...
(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 = {0i1i | i ∊ N}, which is not regular. So, D is false.
View all questions of this test
Which of the following is TRUE?a)Every subset of a regular set is regu...
(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 = {0i1i | i ∊ N}, which is not regular. So, D is false.
Which of the following is TRUE?a)Every subset of a regular set is regu...
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.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).