FA for a language which forms an AGP

Question

Suppose for a set of input symbols Σ={a,b} , L={ε,a,abbb,aabbbbbbbbb,aaabbbbbbbbbbbbbbbbbb,...}

then finite automata for the above language(i.e forms a simple arithmetic geometric progression) will be?

Answer 1

This is a great example of a nonregular language. Intuitively, for a finite-memory computer to determine whether or not a string is in the language, it would need to remember how many a's it saw so that it could determine whether the number of b's was correct. Unfortunately, there are infinitely many possible choices for a number of a's and finite automata can't remember one of infinitely many different options.

You can formally prove this by using either the pumping lemma for regular languages or the Myhill-Nerode theorem. With the pumping lemma, pick a string like a³ⁿ⁺¹b³ⁿ and show that pumping the number of a's breaks the connection to the number of b's. For the Myhill-Nerode theorem, choose the infinite family of strings of the form a³ⁿ⁺¹ and show that tacking on a number of b's appropriate for one string renders the other string not in the language.