Question: Let L = {0n1m, n ≥ 10 m ≤ 50}. Prove that this is a regular language and that any subset of it is also regular.

Answer or approach: 0 is regular, 1 is regular since any symbol in ∑ is regular. Then 1n, n≥10 is regular, because of concatenation of regular languages. Similar argument for 1m. Then 1n1m is regular because concatenation of regular languages is regular.

Not sure about the subset begin regular part...

Is my answer/approach a good place to start, or am I going the wrong way?

Should I design a NFA/DFA for it instead? I think doing so would be harder....

any hints or guidance would be greatly appreciated.


  • 4
    $\begingroup$ It is not true that any subset of $L$ is regular. For example, $\{0^{10+p}\mid p\text{ is prime}\}$ is a subset of $L$ but is not regular. $\endgroup$ – Henning Makholm Nov 17 '15 at 19:23
  • $\begingroup$ You have typos in your argument: you should be talking about $0^n$ not $1^n$. Re subsets: the last claim is very false. There are many examples of subsets of $L$ that are not regular. @HenningMakholm showed one. Here's another: $\{0^n\mid n\in K\}$, where $K$ is an undecidable set of integers, such as the indexes of programs that terminate when run on themselves as input (the halting problem). // Unless it's supposed to be $n\le 10$, in which case $L$ and any subset of it are finite, therefore regular (why?) $\endgroup$ – BrianO Nov 17 '15 at 22:01
  • $\begingroup$ More generally, any infinite language (as in your case) has uncountably many different subsets, while there are only countably many regular languages, so the second part of the exercise holds for no infinite language at all. $\endgroup$ – PhoemueX Nov 18 '15 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.