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.
Looking for an intuitive regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$
formal languages;automata;regular languages;regular expressions
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}$