2
$\begingroup$

Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is divideable by 5. Obviously this is a regular language, and I can also find a simple linear grammer.

My idea for a regular expression was to check all the combinations where I can receive sum zero (in modulo 5) with the digits 1 and 2 and put 0* in between. But is there no better way? Something more elegant?

Edit: My expression is $0^* 1 0^* 1 0^* 1 0^* 1 0^* 1 0^* \cup 0^* 1 0^* 1 0^* 1 0^* 2 0^* \cup 0^* 1 0^* 1 0^* 2 0^* 1 0^* \cup 0^* 1 0^* 2 0^* 1 0^* 1 0^* \cup \ldots $ and so it goes on for all the possible combination. My question is if there is a way to simplify this - Or maybe a different approach?

$\endgroup$
  • $\begingroup$ Could you clarify when is a regular expression 'simple'? We like to be able to evaluate answers objectively, so such a requirement is unfortunately not a good fit unless explicitly defined. It seems you already have a regular expression. Why is this one not 'simple'? $\endgroup$ – Discrete lizard Mar 13 '18 at 10:15
  • 1
    $\begingroup$ Related. If that answers your question, I think you can vote to close as a duplicate and keep things tidy. $\endgroup$ – Peter Taylor Mar 13 '18 at 11:15
  • 1
    $\begingroup$ The thing you give isn't a regular expression, because it's infinitely long. Regular expressions are finite strings; if you allow them to be infinite, they stop being intesting, because you can specify literally any language (even uncomputable ones) as "string 1 or string 2 or string 3 or..." $\endgroup$ – David Richerby Mar 13 '18 at 11:32
  • 3
    $\begingroup$ There probably isn't a nice regular expression for the language you're interested in. There usually isn't, when the property defining the language is "global" in the sense of requiring you to look at the whole string to evaluate it. (Compared to, say, "Strings that don't contain 101", where you only have to check each three-character substring.) $\endgroup$ – David Richerby Mar 13 '18 at 11:36
  • 2
    $\begingroup$ I have now realized that I am not tking into account combinations such as: 22222 or 2221111 that result in sum 10. Going on with this means I will have to consider sum 15 and 20 and so on, which will make my expression infinite and thus wrong (and not just very long..) $\endgroup$ – S.B. Mar 13 '18 at 11:43
1
$\begingroup$

Forget about the $0$, they are boring. Like you said, you can add $0^*$ basically everywhere and you are done.

Now for the $1,2$. Just try to order them in batches that total 5. Then you realised that this might be problematic in case at the count of 4 we read $2$ and overshoot by one. No problem, we remember this, and continue until we reach a proper multiple of five. Note however, that the overshoot just might repeat when we have $212$, or similar.

So here is how the regular expression is constructed: any multiple of five, or when we reach an overshoot, wait until we are back. Repeat.

First some abbreviations:

$E_5= \{11111,1112,1121,1211,2111,221,212,122\}$.

$E_4 = \{1111,112,121,211,22 \}$.

$E_{\mathrm{shoot}}= \{1112,212,122\}$.

Finally here is your expression:

$\Big ( E_5 \cup E_4\cdot 2 \cdot (E_{\mathrm{shoot}})^*\cdot E_4\Big )^* $.

Ah. Add $0^*$, lots of them.

$\endgroup$

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.