# Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|_1$ the number the symbol $1$ occurs in $w$ and by $|w|_0$ the number the symbols $0$ occurs, then $$L = \{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}.$$ I know this language to be regular, as it is quite easy to give an automaton for it. I also got a (quite complicated) regular expression for it using an algorithm going from the automaton. But is there any regular expression that is easy in the sense that it gives some insight into why it is a regular expression for the language?

Not that for example for the language $\{ w \mid |w|_0 \equiv 0 \pmod{3} \}$ it is quite easy to give a regular expression, it would be $1^{\ast}(01^{\ast}01^{\ast}01^{\ast})^{\ast}$, or for $\{ w \mid |w| \equiv 0 \pmod{3} \}$ as it would be $(\Sigma\Sigma\Sigma)^{\ast}$. But the above language somehow combines these conditions.

• I'd be surprised if there was an intuitive regexp for this. The language is defined based on a global property of the string and regular expressions for that kind of property are usually unpleasant. Apr 30, 2017 at 20:33
• I mean a regexp representing that structure somehow, or which could be derived with some arguments about the structure of the language, it need not the be short. Apr 30, 2017 at 23:06

The automaton for that language is, as you say, extremely simple: it consists of a triangle, in which 0s move clockwise and 1s move counterclockwise:

A classic way to turn this into a regular expression is to eliminate states one at a time, converting transitions through each state into regular expressions. Eliminating state 2 is easy since there are no epsilon transitions or self-loops, so we end up with:

\begin{align}s0 \to s0&: 10 \\ s0 \to s1&: 0 + 11 \\ s1 \to s0&: 1 + 00 \\ s1 \to s1&: 01 \\ \end{align}

When we then eliminate state 1, we produce a relatively simple regular expression:

$$(10 + (0+11)(01)^*(1+00))^*$$

Is that regex intuitive? I guess that depends on your intuitions. $10$ and $01$ both have no effect on $2|w|_1 + |w|_0 \pmod{3}$; $0+11$ adds 1, and $1+00$ subtracts 1. So the regex definitely shows the path around the three possible values of $2|w|_1 + |w|_0 \pmod{3}$

• so what about 111100 or 110000 ... Jun 13, 2017 at 19:43
• @phillip: $2*4+2$ is 1 mod 3, and $2*2+4$ is 2. So neither are in $L$. Or am I missimg something?
– rici
Jun 13, 2017 at 22:03
• oops. oops.. oops. I took as number of bits .. my mistake Alright... these would be 00001 1100 111 111000 11110 Jun 13, 2017 at 23:36
• @PhillipWilliams: Grep says those all match. For example, 1100 takes the second alternative, starting with 11 then no repetitions of 01, then 00. Ball's in your court.
– rici
Jun 14, 2017 at 0:16
• Alright, where is 0011 ? (10+(0+11)(01)∗(1+00))∗ does not seem to allow to start with 0 Jun 14, 2017 at 0:33

To complement rici's answer, I just add a run of Kleene's algorithm, giving another regular expression (starting from his automaton):

\begin{align*} R^{-1}_{00} & = \varepsilon \\ R^{-1}_{01} & = 0 \\ R^{-1}_{02} & = 1 \\ R^{-1}_{11} & = \varepsilon \\ R^{-1}_{10} & = 1 \\ R^{-1}_{12} & = 0 \\ R^{-1}_{22} & = \varepsilon \\ R^{-1}_{21} & = 1 \\ R^{-1}_{20} & = 0 \end{align*} and further: \begin{align*} R^2_{00} & = R_{02}^1 (R_{22}^1)^{\ast} R^1_{20} | R_{00}^1 \\ R^1_{00} & = R_{00}^0 (R_{11}^0)^{\ast} R^0_{10} | R_{00}^0 = \varepsilon (10|\varepsilon)^{\ast} 1 | \varepsilon = (10)^{\ast} 1 | \varepsilon \\ R^0_{00} & = R_{00}^{-1} (R_{00}^{-1})^{\ast} R_{00}^{-1} | R_{00}^{-1} = \varepsilon (\varepsilon)^{\ast}\varepsilon | \varepsilon = \varepsilon \\ R^0_{11} & = R_{10}^{-1} (R_{00}^{-1})^{\ast} R_{01}^{-1} | R_{11}^{-1} = 1 (\varepsilon)^{\ast} 0 | \varepsilon = 10 | \varepsilon \\ R^0_{10} & = R_{10}^{-1} (R_{00}^{-1})^{\ast} R_{00}^{-1} | R_{10}^{-1} = 1 (\varepsilon)^{\ast} \varepsilon | 1 = 1 \\ R^1_{02} & = R^0_{10} (R_{11}^0)^{\ast} R_{12}^0 | R_{02}^0 = 1 ( 10|\varepsilon )^{\ast} (11 | 0) | 1 = ( 1 (10)^{\ast}(11 | 0)) | 1\\ R^0_{12} & = R^{-1}_{10} (R_{00}^{-1})^{\ast} R_{02}^{-1} | R_{12}^{-1} = 1 (\varepsilon)^{\ast} 1 | 0 = 11 | 0 \\ R^0_{02} & = R^{-1}_{00} (R_{00}^{-1})^{\ast} R_{02}^{-1} | R_{02}^{-1} = \varepsilon (\varepsilon)^{\ast} 1 | 1 = 1 \\ R^1_{22} & = R^0_{21} (R_{11}^0)^{\ast} R_{12}^0 | R_{22}^0 = (00 | 1)(10|\varepsilon)^{\ast} (11|0) | (01|\varepsilon) = (00 | 1)(10)^{\ast} (11|0) | (01|\varepsilon) \\ R^0_{22} & = R_{20}^{-1} (R_{00}^{-1})^{\ast} R_{02}^{-1} | R_{22}^{-1} = 0 (\varepsilon)^{\ast} 1 | \varepsilon = 01 | \varepsilon \\ R^0_{21} & = R^{-1}_{20} (R_{00}^{-1})^{\ast} R_{01}^{-1} | R_{21}^{-1} = 0 (\varepsilon)^{\ast} 0 | 1 = 00 | 1 \\ R^1_{20} & = R^0_{21} (R_{11}^0)^{\ast} R_{10}^0 | R_{20}^0 = (00|1)(10|\varepsilon)^{\ast} 1 | 0 = (00|1)(10)^{\ast}1 | 0 \\ R^0_{20} & = R^{-1}_{20}(R_{00}^{-1})^{\ast} R_{00}^{-1} | R_{20}^{-1} = 0 (\varepsilon)^{\ast} \varepsilon | 0 = 0 \end{align*} so we have all subterms to give the final answer $$R_{00}^2 = ( ( 1 (10)^{\ast}(11 | 0)) | 1 ) ( (00 | 1)(10)^{\ast} (11|0) | (01|\varepsilon) )^{\ast} ( (00|1)(10)^{\ast}1 | 0 ) | ( (10)^{\ast} 1 | \varepsilon )$$ which is unfortunately much more complicated.