Is the given Language $L$ regular?

Question

$L = \{ a^nb^m : m + n\text{ is divisible by }3 ; m,n\ge 0\}$. Is this language regular, and if so, what is the regular expression?

Answer 1

You should be able to design a finite state automaton that recognizes $L$; doing so proves that $L$ is regular even if you don’t see how to write a regular expression for it. Getting a regular expression for $L$ is perhaps just a little harder. HINT: You’ll a disjunction of three possibilities, one for $n$ divisible by $3$, one for $n\equiv1\pmod3$, and one for $n\equiv2\pmod3$.

Answer 2

Let $A = \{a,b\}$. Then $L$ is the intersection of the two regular languages $a^*b^*$ and $(A^3)^*$. Since the intersection of two regular languages is regular, $L$ is regular. To find a regular expression, just use Brian Scott's useful hint.