1
$\begingroup$

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\}$

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby May 13 '16 at 7:50
  • $\begingroup$ The alphabet is $\{a,b\}$ $\endgroup$ – user3221287 May 13 '16 at 8:05
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! expressing it as $3n+2$ made it a lot clearer! I think $((a+b)3)^*(a+b)^2$ is an acceptable answer? $\endgroup$ – user3221287 May 13 '16 at 16:52
  • $\begingroup$ @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)$. $\endgroup$ – Rick Decker May 13 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.