$a^nb^n$ language vs $a^nb^m$

Question

I always read that $\{a^nb^n \mid n>0\}$ is not a regular language because automata doesn't have memory, while $\{a^nb^m \mid n, m>0\}$ is regular because we don't have to remember anything about the previous states. Can you explain this concept more clearly?

Answer 1

One has $\{a^nb^m \mid n,m > 0\}= a^+b^+$. It follows that this language is regular since it is defined by a regular expression.

The language $\{a^nb^n \mid n > 0\}$ is not regular. A proof using the pumping lemma can be found in the corresponding Wikipedia article. It can also be proved using the Myhill-Nerode theorem. This proof is detailed in the French version of the previous link.

Answer 2

In the second case, words can fall into 5 categories, depend on the number of a's and b's:

1. No a's or b's: Here lies only the empty word.
2. Starting with b: This is the set of all the words of the form "b..." such as: "b", "bb", "babaa"
3. Starting with a, but contain no b's: Those are just the words of the form "a...a"
4. Words which contain some "a" after a "b", this one is tricky. It includes words like "aabbab" and "ba"
5. The last one is the set of words of the desired form: "a...ab...b" Since this is a finite number of states, we can build an automaton with states that represent those categories.

This is almost the thought process one needs to do in order to prove that a language is regular using the Myhill-Nerode Theorem. (One of the categories is contained in others, can you spot which?)

Same reasoning can't be done for the first language, since every $a^nb^n$ live in it's own unique category. So the automaton we're going to built would have to represent infinite number of states.

Answer 3

$a^mb^n$ means that the numbers could be different: there are $m$ a's and $n$ b's, and $m$ and $n$ are not related. Recognizing this is easy, because the machine doesn't have to know what $m$ and $n$ are. It just has to make sure there are no as after the bs.

But $a^nb^n$ means that the number of as and the number of bs are equal; there are $n$ of each. This is like the previous problem, but with the additional constraint that there must be an equal number of each letter. To check that that, the machine must count them and compare the numbers. But however much memory a finite machine has, there is some $n$ that is so big that it will not fit in the machine's memory. At that point the machine will lose count, and get the wrong answer.