GATE IT 2006 | Question: 30

Question

Which of the following statements about regular languages is NOT true ?

• A. Every language has a regular superset
• B. Every language has a regular subset
• C. Every subset of a regular language is regular
• D. Every subset of a finite language is regular

Comments

how  Σ∗   is said as regular??

---

@bhartiDevi 

this DFA accepts$\sum *$

Answer 1

Option C is not True.

• A. Every language has a regular superset: True. $\Sigma^*$ is such a superset.
• B. Every language has a regular subset: True. $\emptyset$ is such a subset.
• C. Every subset of a regular language is regular: False. $a^n b^n \subset \Sigma^*$, but $a^nb^n$ is not Regular.
• D. 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.

Comments

@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 €.

---

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\}$.

---

Thanks @Pragy Agarwal