Let $\Sigma = \{a,b,c,\ldots,x,y,z\}$ be the Latin alphabet, consisting of 26 letters. Consider the language $L$ of all words $\alpha$ over $\Sigma$ satisfying the following constraints:

  • If $\alpha$ contains $a$ then it contains exactly $4$ many $a$s.
  • If $\alpha$ contains $b$ then it contains exactly $8$ many $b$s.
  • ...
  • If $\alpha$ contains $`$ then it contains exactly $2^{27}$ many $z$s.

How do I prove that $L$ is regular?

Note: I did research and I have found that we can use the pumping lemma.

  • 1
    $\begingroup$ It seems unlikely that you can show that the language is regular by using the pumping lemma since it is a necessary but not sufficient condition for a language to be regular. Usually the pumping lemma is shown not to hold for some language $L$, thus proving that $L$ cannot be regular. Try to write your language as a finite union of regular languages. $\endgroup$ – Steven Jan 12 at 23:23

You cannot use the pumping lemma to show that a language is regular. The pumping lemma gives a property of regular languages: if $L$ is regular then $L$ can be "pumped". You can use this to show that $L$ is not regular: if $L$ cannot be pumped, then it is not regular. But you cannot use it to show that $L$ is regular: if $L$ can be pumped, it doesn't follow that $L$ is regular; moreover, there are examples of pumpable languages which are not regular. There are extensions of the pumping lemma which can be used to show that a language is regular, but they are not so useful in practice.

In your case, every word in $L$ contain $0$ or $4$ many $a$s, $0$ or $8$ many $b$s, and so on. In particular, it contains at most $4$ many $a$s, at most $8$ many $b$s, and so on. Therefore every word in $L$ has length at most $4+8+\cdots+2^{27}$. Consequently, $L$ is finite. Every finite language 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.