Assume $ \Sigma=\{0,1\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma?

$$L = \{1^{a_1} 0^{a_2}\ldots 01^{a_k} \mid k \in \mathbb N , a_i \geq 0 , \text{ the $a_i$ are all different}\} $$

  • 1
    $\begingroup$ Should the last $0$ in $L = \{1^{a_1} 0^{a_2}...01^{a_k}|\ ... \}$ be $ 0^{a_k-1}$? $\endgroup$ – Thumbnail Apr 29 '20 at 15:10

The definition of your language is not completely clear, but whatever it is, if you consider $$ L \cap 1^* 0^* = \{ 1^a 0^b \mid a \neq b \} $$ then you immediately see that $L$ is not regular.

If you have to prove it using the pumping lemma, then simply take a proof that works for the above language; it will work for $L$ as well.


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.