Shortest simple regex matching a binary word Task

Define a simple regex as a non-empty regular expression consisting only of


characters 0 and 1,
grouping parentheses ( and ),
one-or-more repetition quantifier +.


Given a non-empty string of 0s and 1s, your program should find the shortest simple regex matching the full input string. (That is, when matching a simple regex, pretend it’s bookended by ^&nbsp;and&nbsp;$.) If there are multiple shortest regexes, print any or all of them.)

code-golf, so the shortest submission (in bytes) wins.

Test cases

1 -&gt; 1
00 -&gt; 00 or 0+
010 -&gt; 010
1110 -&gt; 1+0
01010 -&gt; 01010
0101010 -&gt; 0(10)+ or (01)+0
011111 -&gt; 01+
10110110 -&gt; (1+0)+
01100110 -&gt; (0110)+ or (01+0)+
010010010 -&gt; (010)+
111100111 -&gt; 1+001+ or 1+0+1+
00000101010 -&gt; 0+(10)+ or (0+1)+0
1010110001 -&gt; 1(0+1+)+ or (1+0+)+1
JavaScript (ES6), 488 341 bytes

s=&gt;[s.replace(/(.)\1+/g,'$1+'),...[...Array(60)].map((_,i)=&gt;`(${(i+4).toString(2).slice(1)})+`),...[...Array(1536)].map((_,i)=&gt;`${i&gt;&gt;10?(i&gt;&gt;8&amp;1)+(i&amp;2?'+':''):''}(${i&amp;1}${i&amp;4?i&gt;&gt;4&amp;1:i&amp;16?'+':''}${i&amp;8?''+(i&gt;&gt;7&amp;1)+(i&amp;64?i&gt;&gt;5&amp;1:i&amp;32?'+':''):''})+${i&amp;512?(i&gt;&gt;8&amp;1)+(i&amp;2?'+':''):''}`)].filter(r=&gt;s.match(`^${r}$`)).sort((a,b)=&gt;a.length-b.length)[0]


Explanation: Since six regexes can express all possible binary words, and the longest two are nine characters long, it suffices to check those and all shorter regexes. One candidate is obviously the string with "run length encoding" (i.e. all digit runs replaced with appropriate +s), but also strings with one set of ()s need to be checked. I generate 1596 such regexes (this includes duplicates and useless regexes but they'll just be eliminated) and test all 1597 to see which is the shortest match. The generated regexes fall into two types: \(\d{2,5}\)\+ (60 regexes) and (\d\+?)?\(\d[\d+]?(\d[\d+]?)?\)(\d\+?)? (1536 regexes as I avoid generating regexes with both leading and trailing digit).