I know that to show that a language is not regular, you are supposed to use the pumping lemma, but I cannot figure out how can I show that a language is regular.

How would I show that the following language is regular?

$$ L=\{0^k1^l∣k+l\geq20, \ k,l \in\ \ N\} $$

  • 2
    $\begingroup$ Does this answer your question? How to prove a language is regular? $\endgroup$ – Kevin Wang Jun 9 '20 at 17:48
  • 1
    $\begingroup$ The pumping lemma is a necessary condition for a language to be regular. Therefore you cannot prove that a language $L$ is regular by showing that the pumping lemma holds on $L$. $\endgroup$ – Steven Jun 9 '20 at 18:10

Pumping lemma doesn’t provide us with an if and only if condition for regularity. So, if a language doesn’t satisfy pumping lemma then it isn’t regular, but converse is not true. So, I don’t think we can use pumping lemma to show that a language is regular.

To show given language is regular, you can use Myhill-Nerode theorem, simply come up with a DFA/NFA or a regular expression, or use some closure properties.

For the given language, you can show its regularity using closure property of regular languages (intersection, to be precise): $0^*1^*$ is regular, and so is the $L_{\geq 20} = \{w : |w| \geq 20\}$. It’s quite easy to see that the given language is intersection of these two languages, and hence it is regular.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.