# Finding the Regular Expression of a language

I'm trying to find a regular expression for the language $$L = \{w\mid n_a(w)+n_b(w)\equiv 2\pmod3\}\,,$$ where $n_a(w)$ is the number of $a$s in $w$.

I can see that this would generate strings of length $3n-1$ and I can write the expression for a string of whose length is a multiple of three: $(( a + b )^3)^*$. But that's not quite what I need.

The alphabet is $\{a,b\}$

• What's the alphabet? If it's just $\{a,b\}$, then you just need a regular expression for all strings that have length 2, modulo 3. If it's $\{a,b,c\}$, then life's a bit trickier. May 13, 2016 at 7:50
• The alphabet is $\{a,b\}$ May 13, 2016 at 8:05

It's better to think of $L$ as strings of length $3n+2$. You already have an expression for strings whose length is a multiple of 3, so use that and append all strings of length 2.
• Thank you! expressing it as $3n+2$ made it a lot clearer! I think $((a+b)3)^*(a+b)^2$ is an acceptable answer? May 13, 2016 at 16:52
• @user3221287. That depends on your audience. If you want to strictly adhere to the usual definition of a regular expression, you could always write out the full solution as $(aaa+aab+aba+abb+baa+bab+bba+bbb)^*(aa+ab+ba+bb)$. May 13, 2016 at 16:58