29 votes 29 votes Which of the following statements about regular languages is NOT true ? Every language has a regular superset Every language has a regular subset Every subset of a regular language is regular Every subset of a finite language is regular Theory of Computation gateit-2006 theory-of-computation easy regular-language + – Ishrat Jahan asked Oct 31, 2014 • retagged Jul 1, 2017 by Silpa Ishrat Jahan 8.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply bhartiDevi commented Dec 29, 2018 reply Follow Share how Σ∗ is said as regular?? 1 votes 1 votes neeraj33negi commented Dec 29, 2018 reply Follow Share @bhartiDevi this DFA accepts$\sum *$ 3 votes 3 votes Please log in or register to add a comment.
Best answer 68 votes 68 votes Option C is not True. Every language has a regular superset: True. $\Sigma^*$ is such a superset. Every language has a regular subset: True. $\emptyset$ is such a subset. Every subset of a regular language is regular: False. $a^n b^n \subset \Sigma^*$, but $a^nb^n$ is not Regular. Every subset of a finite language is regular: True. Every subset of a finite set must be finite by definition. Every finite set is regular. Hence, every subset of a finite language is regular. Pragy Agarwal answered Dec 27, 2014 • edited Mar 8, 2018 by kenzou Pragy Agarwal comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments soumayan bandhu commented Jan 29, 2019 reply Follow Share @Pragy Agarwal if my language is L={a^nb^n l n>0} then how can we say ' phi' is subset of this language? Because it doesn't accept €. 1 votes 1 votes Pragy Agarwal commented Jan 29, 2019 reply Follow Share empty set: $\emptyset$ phi: $\phi$ (phi is not used to represent an empty set. The symbol for empty set is called emptyset) Empty set $\emptyset = \{\}$ Language that accepts only $\varepsilon$ = $\{\varepsilon\}$ Obviously, $\{\} \neq \{\varepsilon\}$ Given a set $S = \{1, 2\}$, the subsets are $\{\}, \{1\}, \{2\}, \{1, 2\}$. Note that $\emptyset$ is a subset of set $S$, and is a subset of any set $S$. Similarly, your language $L$ has $\{\}$ as one of its subsets, no matter what $L$ is. However, if $L$ contains the empty string $\varepsilon$, then it will also have a subset containing only the empty string, which is $\{\varepsilon\}$. If $L$ doesn't contain $\varepsilon$, then $\{\varepsilon\}$ will not be a subset of $L$. You're essentially confusing between $\{\}$ and $\{\varepsilon\}$. 9 votes 9 votes soumayan bandhu commented Jan 29, 2019 reply Follow Share Thanks @Pragy Agarwal 1 votes 1 votes Please log in or register to add a comment.