Question: Write a regular expression for bit strings representing numbers divisible by 3.
Answer: First draw the finite automaton. This automaton has start state Sx and accepting state S0 and is similar to the answer for divisibility by 5.
__ +---------+ +-------+ __
/ 0\ |1 v v 0| /1 \
\-->S0<---Sx-->S1 S2<--/
^ 0 1 | | ^
| 1| |0 |
+---------+ +-------+
To get to S0 from Sx the first time we must go through
the regular expression ``0|1(01*0)*1''.
Then after any time we go through ``0'' or ``1(01*0)*1'' we get back to
S0. So the accepting expression is
(0|1(01*0)*1)(0|1(01*0)*1)*