1
$\begingroup$

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.

$\endgroup$
9
  • 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$ Commented Oct 21, 2014 at 21:20
  • $\begingroup$ Ahhhhh, I see. Let me rework that. $\endgroup$
    – KDecker
    Commented 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
    Commented Oct 21, 2014 at 21:22
  • $\begingroup$ That’s right: the language really isn’t regular (though it is context-free). $\endgroup$ Commented 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
    Commented Oct 21, 2014 at 21:24

1 Answer 1

1
$\begingroup$

(A)

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

$m=n$

$m\ne n$

$m\ge n$

$m\le n$ etc.

(B)

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .