computer-scienceregular-languagedfaformal-languagespumping-lemma

Is L = {a^n a^n b^m |m, n ≥ 0} a regular or irregular language?


I have troubles in solving/proving this problem. I can understand that in a non regular no Finite State Automaton/Machine can be written that validates and accepts this input since it lacks a memory component. (Please correct me if I'm wrong)

The wikipedia entry on Regular Language also lists this example, but does not provide a (mathematical) proof why it is not regular.


Solution

  • This language is accepted by the regular expression (aa)*b*, so yes, it is a regular language.