2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 30 '17 at 20:33
  • $\begingroup$ 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. $\endgroup$ – StefanH Apr 30 '17 at 23:06
5
$\begingroup$

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:

DFA for language

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

Improve this answer
$\endgroup$
11
  • $\begingroup$ so what about 111100 or 110000 ... $\endgroup$ – Phillip Williams Jun 13 '17 at 19:43
  • $\begingroup$ @phillip: $2*4+2$ is 1 mod 3, and $2*2+4$ is 2. So neither are in $L$. Or am I missimg something? $\endgroup$ – rici Jun 13 '17 at 22:03
  • $\begingroup$ oops. oops.. oops. I took as number of bits .. my mistake Alright... these would be 00001 1100 111 111000 11110 $\endgroup$ – Phillip Williams Jun 13 '17 at 23:36
  • $\begingroup$ @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. $\endgroup$ – rici Jun 14 '17 at 0:16
  • $\begingroup$ Alright, where is 0011 ? (10+(0+11)(01)∗(1+00))∗ does not seem to allow to start with 0 $\endgroup$ – Phillip Williams Jun 14 '17 at 0:33
1
$\begingroup$

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.

Improve this answer
$\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.