# How to show that a language is regular

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

• Does this answer your question? How to prove a language is regular? – Kevin Wang Jun 9 '20 at 17:48
• 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$. – Steven Jun 9 '20 at 18:10

## 1 Answer

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.