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

$\endgroup$
2
  • $\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$ May 13, 2016 at 7:50
  • $\begingroup$ The alphabet is $\{a,b\}$ $\endgroup$ May 13, 2016 at 8:05

1 Answer 1

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.

$\endgroup$
2
  • $\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$ May 13, 2016 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$ May 13, 2016 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.