0
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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