I am trying to find a short regular expression that matches to all binary sequences that are dividable by 3.
This is homework. It would be great if I could only get some hints before the final solution :D
Using the DFA I would get the following states
|0|1
A|A|B
B|C|A
C|B|C
That would give
$$A=0A+1B\\ B=0C+1A\\ C=0B+1C $$
I eliminate the recursion of $1C$ which is $1*$ and $0A$ which is $0*$
$$ A=0*+1B\\ B=0C+1A\\ C=0B+1*$$
I replace C in B
$$B=0(0B+1*)+1A$$
I need to get rid of the $0B$ somehow to be able to place it into A. $0B$ part should be again a recurision.. But I am lost from here on.
Any hints?
Thanks a lot
From $C=0B+1C$ we have $$ C = 1^*0B $$ Then $B=0C+1A$ becomes $B=1^*0B+1A$, from which he find $$ B = (1^*0)^*1A$$ Now $A=0A+1B+\epsilon$ becomes $A= 0A+(1^*0)^*1A +\epsilon= (0 | (1^*0)^*1)A+\epsilon $ and from this ultimately $$A=(0 | (1^*0)^*1)^*$$ (or with the last $^*$ replaced with $^+$ if you want to avoid $\epsilon$ as match)