i write regex ((((11)*1)((00)*0)(1*)((00)*0)((11)*1))|((0*)11(0*))|(0*))
to check strings like "101111000110000101001110" is divisible by 3, but i have to optimize it
UPD: yes, expression is correct, its question on codewars
Depending on the current state of X, and the digit (either 0 or 1) we are about to append to the binary form of X, we have our nice
Now let's play: departing from state "0", we want to travel through the DFA and eventually make our way back to state "0", what are the possible routes?
The routes can be classified into the below 2 categories, in which "[some route]" means it can be repeated:
- route a. itself
- b. → [d. → [f.] → e.] → c.
Now we are ready to "translate" the possible routes (including route repeatability!) into their corresponding regular expressions:
0
1(01*0)*1
Which combines into: 0|1(01*0)*1
; we also add
to the entire pattern because the pattern itself can also be repeated.