1

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.

KDecker
  • 861
  • 2
  • 11
  • 23
  • 2
    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}$. – Brian M. Scott Oct 21 '14 at 21:20
  • Ahhhhh, I see. Let me rework that. – KDecker Oct 21 '14 at 21:21
  • I can't can I.. There is no way that you could assure there are the same number of $b$s as $a$s.? – KDecker Oct 21 '14 at 21:22
  • That’s right: the language really isn’t regular (though it is context-free). – Brian M. Scott Oct 21 '14 at 21:23
  • 1
    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. – MJD Oct 21 '14 at 21:24
  • And that idea is what the pumping lemma states? – KDecker Oct 21 '14 at 21:33
  • A side question, the $|x|$, where $x$ is a string in the language, is the length of the string $x$? As in the first few steps of the pumping lemma. – KDecker Oct 21 '14 at 21:46
  • Yes, $\lvert x\rvert $ is the length of $x$. – MJD Oct 21 '14 at 22:04
  • Yes, the pumping lemma is a formalization of the idea that any machine, fed a long enough string, must lose track somewhere not too far from the beginning. – MJD Oct 21 '14 at 22:05

1 Answers1

1

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

Hailey
  • 1,020