How can you prove that $L=\{a^n b^{2n} \}$ is not regular without the use of pumping lemma?

  • 1
    $\begingroup$ This language is finite hence regular. Did you mean $\{a^nb^{2n}\mid n\in \mathbb{N}\}$? $\endgroup$ – Nathaniel May 18 at 17:23
  • 2
    $\begingroup$ cs.stackexchange.com/q/1031/755 $\endgroup$ – D.W. May 18 at 18:59

There are several ways to prove a language is not regular:

  • the pumping lemma is one of them;
  • you can use closure properties of regular languages. For example, if $L_1$ and $L_2$ are regular then $L = L_1 \cap L_2$ must be regular. That means that if $L$ is not regular, then either $L_1$ or $L_2$ is not regular;
  • you can use the Myhill-Nerode theorem;
  • you can suppose a language is recognized by a DFA, and conclude to a contradiction (the DFA must have at least $n$ states for all $n\in\mathbb{N}$, it must recognize words not in the language, …)
  • $\begingroup$ In case you were not aware, we have an elaborate reference posting for questions like this, so you don't need to spend your time answering uninspired questions like the above over and over again. :) $\endgroup$ – Raphael May 18 at 21:46
  • $\begingroup$ I realized it with @D.W.'s comment… Thanks for the reminder! $\endgroup$ – Nathaniel May 18 at 22:07

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