Regular Languages

Question

Why is a^mbⁿ / m,n>=1 a regular language but aⁿbⁿ / n>=1 not?

Answer 1

 a^mbⁿ / m,n>=1

The strings in this language are {ab, aab, abb, aabb, aaab, abbb ... }. The language for this would be :

S -> aS / aB

B -> bB / b

we can make a NFA  for this language so it is regular.

aⁿbⁿ / n>=1

The strings in this language will be { ab, aabb, aaabbb ...}. For every string in this language we have to check whether the number of a's are equal to the number of b's which would require some memory to store the number of a's for checking with b's which cannot be done by a NFA so this is not regular.

Comments

true ,but what if m=n? it is same as a^nb^n right? how could we use FA to represent this case as well?

Answer 2

because for a^mbⁿ  you  don't have to count i.e keep track of values of n and m they can be anything

but in case aⁿbⁿ we have to count #a's and #b''s  and to count we need memory  i.e. stack and it is known if any language can't be 

represented as finite automata is not REGULAR