Why is {a^n a^n | n >= 0} regular?

问题:

I understand the reason and the proof why {a^n b^n | n >= 0} is NOT regular. Why is {a^nb^n | n >= 0} not regular?

The solution of one of my exercises is: {a^n a^n | n >= 0} is regular. How can I prove this thesis?

回答1:

Yes, Language {aⁿ aⁿ | n >= 0} is a regular language. To proof that certain language is regular, you can draw its dfa/regular expression. And you can drive do for this language as follows:

Because "anan for n >= 0" is same as "a2n for n >=0", and that is "set of all string contests of even number of symbol a" that is regular — regular expression for this is (aa)*.

Note, regular expressions is only possible for regular languages hence it is proved that {aⁿ aⁿ | n >= 0} is a regular language. and DFA would be:

I would suggest you to read this why languages like {aⁿ bⁿ | n >= 0} are not regular.

回答2:

First change the definition to the equivalent L = {a^2n | n >= 0}. Now observe that any string that belongs to L is simply a multiple of 2 as. Then change that definition to (aa)*, which is a regular expression since it only uses primitives for expressing regular languages - individual characters (a), concatenation (aa) and Kleene star (*). Now you're done.