Given that $L$ is a regular language and $X \subseteq L$,does $X$ have to be also regular?
Asked
Active
Viewed 47 times
1 Answers
4
No. $\Sigma^\ast$ is regular, but not all $L \subseteq \Sigma^\ast$ are regular.
Henry Swanson
- 12,972
-
1Could you give me a counterexample? – evinda Jan 20 '14 at 11:55
-
2The language ${ 0^i 1^i \mid i \in \mathbb{N} }$ is not regular. You can show this using the pumping lemma. – Henry Swanson Jan 20 '14 at 22:14
-
Thank you very much!! I have also an other question..Do I have to write which is the $\Sigma$ of the language,or is it enough to say that $\Sigma^{}$ is a regular language and ${0^i1^i|i \in N} \subseteq \Sigma^{}$?? – evinda Jan 26 '14 at 10:42
-
1As long as $0$ and $1$ are in $\Sigma$. – Henry Swanson Jan 26 '14 at 21:32