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