I am reading about the pumping lemma, and having a hard time understanding it. I noticed that it is used to prove a language is not regular by contradiction. So you must first prove that a language in not regular by defying one of the rules that makes a language regular.

Given as a instance of doing this on the Wikipedia page for the pumping lemma is the language produced by $a^nb^n : n\geq 0$. They apply the pumping lemma to prove that it is not a regular language. I can see why that the language does not produce a regular expression (L($a^*) \cup L(b^*)$ does not produce an example string $aaabbb$). But not in the sense of the pumping lemma.

I then remembered, and am now questioning, the idea that you can convert any NFA to a DFA (thus making $a^nb^n : n\geq 0$ regular somehow, thus disproving what people who know what they are talking about). I tried to work it out on paper, and have managed to "do it" but I would figure this is wrong.

enter image description here

I would figure that if that was properly done then the number of states produced by the NFA when converting is infinite as a result of following epsilon transitions. Thus it is convertible but it creates infinite states as a DFA? Which violates the law that it is not rational, it has infinite states?...

If that is the case then does the pumping lemma state that if I can create a " uncontrollable pumpable" string within the language then I will have infinite states, thus not regular.

  • 2
    $\begingroup$ There is no NFA that recognizes precisely the language $\{a^nb^n:n\ge 0\}$. Your automata appear to be recognizing the very different language $\{(ab)^n:n\ge 0\}$. $\endgroup$ Oct 21, 2014 at 21:20
  • $\begingroup$ Ahhhhh, I see. Let me rework that. $\endgroup$
    – KDecker
    Oct 21, 2014 at 21:21
  • $\begingroup$ I can't can I.. There is no way that you could assure there are the same number of $b$s as $a$s.? $\endgroup$
    – KDecker
    Oct 21, 2014 at 21:22
  • $\begingroup$ That’s right: the language really isn’t regular (though it is context-free). $\endgroup$ Oct 21, 2014 at 21:23
  • 1
    $\begingroup$ There is no way to recognize the language $\mathtt{a}^n\mathtt{b}^n$ with an NFA. You can use the Myhill-Nerode theorem or the pumping lemma to show this, but the intuitive idea is very simple: such a machine has to work by counting the as, then counting the bs to see if there are the same number of each. But a finite machine has an upper limit on the size of the numbers it can store. If the finite machine has enough memory to store a number up to a maximum of $M$, then it will lose count when trying to recognize $\mathtt{a}^n\mathtt{b}^n$ for $n>M$ and get the wrong answer. $\endgroup$
    – MJD
    Oct 21, 2014 at 21:24

1 Answer 1



$\{a^mb^n : m,n \ge 0\}$ is not-regualr if $m,n$ have any relation between them.Such that,


$m\ne n$

$m\ge n$

$m\le n$ etc.


But if $m,n $ have not any relation then it will be regular language and it could be read as string with any number of $a$ followed by any number of $b$.

For your knowledge let's take an example,

$L_1=\{a^n:n\ge 0\}$

$L_2=\{b^n:n\ge 0\}$

then what is $L_1.L_2$(concat)?

It will not be $\{a^nb^n : n \ge 0\}$,it will be any number of $a$ followed by any number of $b$.


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.