75

Matthias Goergens ma 25 604 znaków (w porównaniu z pierwotną liczbą 63 993 znaków), aby dopasować liczby podzielne przez 7, ale obejmuje to wiele puchu: nadmiarowe nawiasy, dystrybucja ( xx|xy|yx|yyzamiast [xy]{2}) i inne problemy, chociaż jestem pewien, że nowy start byłby pomocny w oszczędzaniu miejsca. Jak mały można to zrobić?

Dowolna rozsądna różnorodność wyrażeń regularnych jest dozwolona, ale nie ma kodu wykonywalnego w wyrażeniu regularnym.

Wyrażenie regularne powinno pasować do wszystkich ciągów zawierających dziesiętną reprezentację liczby podzielnej przez 7 i żadnych innych. Dodatkowy kredyt za wyrażenie regularne, które nie pozwala na początkowe zera.

code-golf math regular-expression Charles
źródło

Jaka jest dokładna intencja? Czy musi pasować do wszystkich liczb dowolnego rozmiaru podzielnych przez 7, czy na przykład tylko do prawidłowych 32-bitowych odcieni?

Peter Taylor,

2

@Peter Taylor: Powinien pasować do wszystkich ciągów, które są dziesiętną reprezentacją liczby podzielnej przez 7. Dodatkowy kredyt dla rozwiązań, które uniemożliwiają wiodące zera.

Charles,

1

Czy przypadkiem ... czy regex nie pasuje do liczb niepodzielnych przez 7?

stoisko

@boothby: Oczywiście, możesz użyć pustego wyrażenia.

Charles

2

@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ Tak, 0 powinno być dozwolone w obu wersjach.

Charles

24

10791 znaków, dozwolone zera wiodące

(0|7|46*[29]|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18]))|(2|9|46*4)(3|56*4)*(1|8|56*[29])|(3|46*5|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))|(2|9|46*4)(3|56*4)*(4|56*5)|(5|46*[07]|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(2|9|46*4)(3|56*4)*(6|56*[07]))(4|36*[07]|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))|(1|8|36*4)(3|56*4)*(4|56*5)))(1|8|(0|7|[29]6*4)(3|56*4)*(4|56*5)|[29]6*5|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(5|34*6|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(1|8|64*6|(5|64*3)(6|[07]4*3)*(2|9|[07]4*6))|(2|9|34*3)(6|[07]4*3)*(2|9|[07]4*6)|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29]))))|(5|46*[07]|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(2|9|46*4)(3|56*4)*(6|56*[07]))(4|36*[07]|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18]))|(1|8|36*4)(3|56*4)*(1|8|56*[29]))|(6|46*[18]|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07]))|(2|9|46*4)(3|56*4)*(0|7|56*[18])|(3|46*5|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))|(2|9|46*4)(3|56*4)*(4|56*5)|(5|46*[07]|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(2|9|46*4)(3|56*4)*(6|56*[07]))(4|36*[07]|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))|(1|8|36*4)(3|56*4)*(4|56*5)))(1|8|(0|7|[29]6*4)(3|56*4)*(4|56*5)|[29]6*5|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(4|34*5|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(0|7|64*5|(5|64*3)(6|[07]4*3)*(1|8|[07]4*5))|(2|9|34*3)(6|[07]4*3)*(1|8|[07]4*5)|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18]))))|(5|46*[07]|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(2|9|46*4)(3|56*4)*(6|56*[07]))(4|36*[07]|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07]))|(1|8|36*4)(3|56*4)*(0|7|56*[18])))(2|9|53*[07]|(0|7|53*5)(6|43*5)*(1|8|43*[07])|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18]))|(4|[07]6*3|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(5|[07]6*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18])))|(6|53*4|(0|7|53*5)(6|43*5)*(5|43*4)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(4|[07]6*3|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(5|[07]6*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))(1|8|(0|7|[29]6*4)(3|56*4)*(4|56*5)|[29]6*5|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(4|34*5|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(0|7|64*5|(5|64*3)(6|[07]4*3)*(1|8|[07]4*5))|(2|9|34*3)(6|[07]4*3)*(1|8|[07]4*5)|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18])))))*(3|53*[18]|(0|7|53*5)(6|43*5)*(2|9|43*[18])|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29]))|(4|[07]6*3|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(5|[07]6*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29])))|(6|53*4|(0|7|53*5)(6|43*5)*(5|43*4)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(4|[07]6*3|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(5|[07]6*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))(1|8|(0|7|[29]6*4)(3|56*4)*(4|56*5)|[29]6*5|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(5|34*6|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(1|8|64*6|(5|64*3)(6|[07]4*3)*(2|9|[07]4*6))|(2|9|34*3)(6|[07]4*3)*(2|9|[07]4*6)|(6|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|[29]6*3|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29]))))))+

10795 znaków, zera wiodące zabronione

0|((foo)0*)+, gdzie znajduje się powyższe wyrażenie regularne (0|foo)+.

Wyjaśnienie

Liczby podzielne przez 7 są dopasowywane przez oczywisty automat skończony z 7 stanami Q = {0,…, 6}, stan początkowy i końcowy 0 oraz przejścia d: i ↦ (10i + d) mod 7. Przekształciłem ten automat skończony na wyrażenie regularne, wykorzystujące rekurencję na zbiorze dozwolonych stanów pośrednich:

Biorąc pod uwagę i, j ∈ Q i S ⊆ Q, niech f (i, S, j) będzie wyrażeniem regularnym, które pasuje do wszystkich ścieżek automatów od i do j przy użyciu tylko stanów pośrednich w S.

f (i, ∅, j) = (j - 10i) mod 7,

f (i, S ∪ {k}, j) = f (i, S, j) ∣ f (i, S, k) f (k, S, k) * f (k, S, j).

Użyłem programowania dynamicznego, aby wybrać k, aby zminimalizować długość wynikowego wyrażenia.

Anders Kaseorg
źródło

Myślę, że musisz dodać 2 znaki w wiodącym przypadku zero, ponieważ myślę, że zero musi być dozwolone0|((foo)0*)+

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳

3

Skomentowałem to pytanie, ale zgodnie ze zdrowym rozsądkiem „brak wiodącego zera” zwykle oznacza, że nie ma zbędnego wiodącego zera, ale nie wyklucza liczby zerowej.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳

95

13 755 12 699 12 731 znaków

Ta regex nie odrzuca wiodącego zera.

(0|7|[18]5*4|(2|9|[18]5*6)(3|[29]5*6)*(1|8|[29]5*4)|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4)))|(5|[18]5*[29]|(2|9|[18]5*6)(3|[29]5*6)*(6|[29]5*[29])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(6|[07]5*4|(1|8|[07]5*6)(3|[29]5*6)*(1|8|[29]5*4)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))))|(6|[18]5*3|(2|9|[18]5*6)(3|[29]5*6)*(0|7|[29]5*3)|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))|(5|[18]5*[29]|(2|9|[18]5*6)(3|[29]5*6)*(6|[29]5*[29])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(4|[18]5*[18]|(2|9|[18]5*6)(3|[29]5*6)*(5|[29]5*[18])|(3|[18]5*[07]|(2|9|[18]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(5|[07]5*3|(1|8|[07]5*6)(3|[29]5*6)*(0|7|[29]5*3)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))))(2|9|45*3|(5|45*6)(3|[29]5*6)*(0|7|[29]5*3)|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))|(1|8|45*[29]|(5|45*6)(3|[29]5*6)*(6|[29]5*[29])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(5|[07]5*3|(1|8|[07]5*6)(3|[29]5*6)*(0|7|[29]5*3)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(1|8|35*3|(4|35*6)(3|[29]5*6)*(0|7|[29]5*3)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(4|65*3|(0|7|65*6)(3|[29]5*6)*(0|7|[29]5*3)))))*(3|45*4|(5|45*6)(3|[29]5*6)*(1|8|[29]5*4)|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4)))|(1|8|45*[29]|(5|45*6)(3|[29]5*6)*(6|[29]5*[29])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(0|7|45*[18]|(5|45*6)(3|[29]5*6)*(5|[29]5*[18])|(6|45*[07]|(5|45*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))(4|[07]5*[29]|(1|8|[07]5*6)(3|[29]5*6)*(6|[29]5*[29])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(0|7|35*[29]|(4|35*6)(3|[29]5*6)*(6|[29]5*[29])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(3|65*[29]|(0|7|65*6)(3|[29]5*6)*(6|[29]5*[29]))))*(6|[07]5*4|(1|8|[07]5*6)(3|[29]5*6)*(1|8|[29]5*4)|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))|(3|[07]5*[18]|(1|8|[07]5*6)(3|[29]5*6)*(5|[29]5*[18])|(2|9|[07]5*[07]|(1|8|[07]5*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))(6|35*[18]|(4|35*6)(3|[29]5*6)*(5|[29]5*[18])|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(2|9|65*[18]|(0|7|65*6)(3|[29]5*6)*(5|[29]5*[18])))*(2|9|35*4|(4|35*6)(3|[29]5*6)*(1|8|[29]5*4)|(5|35*[07]|(4|35*6)(3|[29]5*6)*(4|[29]5*[07]))(1|8|65*[07]|(0|7|65*6)(3|[29]5*6)*(4|[29]5*[07]))*(5|65*4|(0|7|65*6)(3|[29]5*6)*(1|8|[29]5*4))))))*

Jest to testowane z The Regex Coach .

Jak się tam dostaniemy

Powyższy Regeks powstały najpierw przez skonstruowanie DFA, który zaakceptowałby żądane dane wejściowe (dziesiętne podzielne przez 7), a następnie przekonwertował na wyrażenie regularne i naprawił notację

Aby to zrozumieć, najpierw należy utworzyć DFA, który akceptuje następujący język:

L = {w | w is a binary representation of an integer divisible by 7 }

Oznacza to, że „dopasuje” liczby binarne, które można podzielić przez 7.

DFA wygląda następująco:

Mod 7 NFA

Jak to działa

Zachowujesz bieżącą wartość, Aktóra reprezentuje wartość bitów odczytanych przez DFA. Kiedy czytasz 0a, A = 2*Aa kiedy czytasz 1 A = 2*A + 1. Na każdym kroku, który obliczysz A mod 7, przechodzisz do stanu reprezentującego odpowiedź.

Więc uruchomienie testowe:

Czytamy, w 10101którym jest reprezentacja binarna dla 21 w systemie dziesiętnym.

q0Obecnie zaczynamy od stanuA=0
Czytamy 1, ze „zasady” powyżej A = 2*A + 1tak A = 1. A mod 7 = 1więc przechodzimy do stanuq1
Czytamy 0, A = 2*A = 2, A mod 7 = 2więc możemy przejść doq2
Czytać 1, A = 2*A + 1 = 5, A mod 7 = 5, przenieść doq5
Czytać 0, A = 2*A = 10, A mod 7 = 3, przenieść doq3
Czytać 1, A = 2*A + 1 = 21, A mod 7 = 0, przenieść doq0
Dane wejściowe są akceptowane, więc liczba 10101jest podzielna przez 7!

Przekształcanie DFA w wyrażenie regularne jest trudnym zadaniem, więc poprosiłem JFLAP, aby zrobił to za mnie:

(0|111|100((1|00)0)*011|(101|100((1|00)0)*(1|00)1)(1((1|00)0)*(1|00)1)*(01|1((1|00)0)*011)|(110|100((1|00)0)*010|(101|100((1|00)0)*(1|00)1)(1((1|00)0)*(1|00)1)*(00|1((1|00)0)*010))(1|0(1((1|00)0)*(1|00)1)*(00|1((1|00)0)*010))*0(1((1|00)0)*(1|00)1)*(01|1((1|00)0)*011))*

Dla liczb dziesiętnych

Proces jest prawie taki sam:

Zbudowałem DFA, który akceptuje język:

L = {w | w is a decimal number that is divisible by 7}

Oto DFA:

Logika jest podobna, ta sama liczba stanów, tylko wiele więcej przejść do obsługi wszystkich dodatkowych cyfr, które przynoszą liczby dziesiętne.

Teraz zasada zmienić Ana każdym kroku jest: kiedy czytasz cyfrę dziesiętną n: A = 10*A + n. Potem znowu tylko mod Ao 7 i przejdź do następnego stanu.

Rewizje

Wersja 5

Powyższe wyrażenie regularne odrzuca teraz liczby wiodące zera - oczywiście oprócz samego zera.

To sprawia, że DFA jest nieco inny, w zasadzie rozgałęziasz się od początkowego węzła, gdy czytasz pierwsze zero. Odczyt kolejnego zera wprowadza cię w nieskończoną pętlę w stanie rozgałęzionym. I nie stały schemat aby pokazać to.

Wersja 7

Zrobiłem trochę „metaregex” i skróciłem regex, zastępując niektóre związki klasami postaci.

Wersja 10 i 11 (autor: nhahtdh)

Modyfikacja autora polegająca na odrzuceniu wiodącego zera jest nieprawidłowa. Powoduje, że wyrażenia regularne nie pasują do poprawnych liczb, takich jak 1110 (dziesiętny = 14) w przypadku wyrażenia binarnego i 70 w przypadku wyrażenia dziesiętnego. Ta wersja przywraca modyfikację, a tym samym umożliwia dopasowanie dowolnych zer wiodących i pustych ciągów znaków.

Ta wersja zwiększa rozmiar wyrażenia dziesiętnego, ponieważ poprawia błąd w oryginalnym wyrażeniu regularnym, spowodowany brakiem krawędzi (9) od stanu 5 do stanu 3 w oryginalnym DFA.

Gryf
źródło

Wyjaśnię pytanie, aby określić liczbę dziesiętną. Tak, jest znacznie łatwiej w bazach b, gdzie 7 | b (b-1).

Charles,

Poprawiłem swoją odpowiedź. Dziesiętny jest w porządku: D

Griffin

Za późno, abym poprawił swój komentarz, chociaż ... Miałem na myśli 7 | B (B-1), gdzie B jest małą potęgą b. Binary ma krótki regex od 7 | 8 (8-1). Dziesiętny jest większy od 7 | 999999000000 to najmniejszy, który działa.

Charles,

3

btw, myślę, że użyłeś DFA , a nie NFA

kod binarny

2

Żadne z wyrażeń regularnych pokazanych w tej odpowiedzi nie jest poprawne. Binarny nie pasuje 1110, a ten po przecinku nie pasuje 70. Zostało to przetestowane zarówno w Pythonie, jak i Perlu. (python wymagał konwersji co (do (?:pierwszej)

Daniel Martin

35

Wyrażenie regularne .NET, 119 118 105 bajtów

^(?>(?=[1468](?<4>)|)(?=[2569](?<4>){2}|)([3-6]()|\d)((?<-2>)(){3}|){7}((?<-4>){7}|(?<2-4>)|){9})+$(?!\2)

111 znaków nie zezwalających na początkowe 0:

^(?!0.)(?>(?=[1468](?<4>)|)(?=[2569](?<4>){2}|)([3-6]()|\d)((?<-2>)(){3}|){7}((?<-4>){7}|(?<2-4>)|){9})+$(?!\2)

113 znaków nie zezwala na początkowe zera i obsługuje liczby ujemne:

^-?(?>(?=[1468](?<4>)|)(?=[2569](?<4>){2}|)([3-6]()|\d)((?<-2>)(){3}|){7}((?<-4>){7}|(?<2-4>)|){9})+$(?!\2)

Wypróbuj tutaj.

Objaśnienie (poprzedniej wersji)

Wykorzystuje techniki stosowane przez różne odpowiedzi w tym pytaniu: Cops and Robbers: Reverse Regex Golf . Wyrażenie regularne .NET ma funkcję o nazwie grupa bilansująca, której można używać do wykonywania arytmetyki. (?<a>)popycha grupę a. (?<-a>)wyświetla to i nie pasuje, jeśli wcześniej nie było grupy a.

(?>...)Dopasuj i nie cofaj się później. Dlatego zawsze będzie pasować tylko do pierwszej dopasowanej alternatywy.
((?<-t>)(){3}|){6} Pomnóż liczbę grupy t przez 3. Zapisz wynik w liczbie grup 2.
(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d) Dopasuj liczbę i tę liczbę z grupy 2.
((?<-2>){7}|){3} Usuń grupę 2 wielokrotnie 7 razy.
((?<t-2>)|){6} Usuń grupę 2 i dopasuj tę samą liczbę do grupy t.
$(?(t)a)Jeśli nadal istnieje dopasowana grupa t, dopasuj apo końcu łańcucha, co jest niemożliwe.

Myślałem, że ta 103-bajtowa wersja powinna również działać, ale nie znalazłem obejścia błędu w kompilatorze.

^(?(?(?((?<3>){2}[2569]|)([3-6])?((?<-1>)(){3}|){7})(?<3>[1468])?((?<-3>){7}|(?<1-3>)|){9})\d)+$(?(1)a)

jimmy23013
źródło

Bardzo krótki. Chciałbym wyjaśnić, jak to działa!

Charles

@Charles Edited.

jimmy23013

Nie sądzę, że to zostanie pokonane, ale wolę przynajmniej wdrożyć DFA z rekurencją, to po prostu szalone. Zastanawiam się, czy ktoś może udowodnić lub obalić wyrażenia regularne .NET po ukończeniu Turinga.

ThePlasmaRailgun

@ ThePlasmaRailgun .NET regex nie jest zakończony Turinga, ponieważ nie pozwala na powtarzanie pustych przechwyceń więcej niż dolna granica ( przykład ). Tak więc każda grupa z kwantyfikatorami może mieć tylko skończoną liczbę alternatyw, jeśli dane wejściowe mają stałą długość.

jimmy23013

Ach Bez tego ograniczenia Turing byłby kompletny?

ThePlasmaRailgun

30

468 znaków

Smak wyrażenia regularnego Ruby pozwala na rekursję (chociaż jest to rodzaj oszustwa), więc łatwo jest wdrożyć DFA, który rozpoznaje liczby podzielne przez 7 za pomocą tego. Każda nazwana grupa odpowiada stanowi, a każda gałąź na przemian zużywa jedną cyfrę, a następnie przeskakuje do odpowiedniego stanu. Po osiągnięciu końca liczby wyrażenie regularne pasuje tylko wtedy, gdy silnik znajduje się w grupie „A”, w przeciwnym razie nie powiedzie się.

Rozpoznaje zera wiodące.

(?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)

Lowjacker
źródło

3

Chciałem to zabronić, ale chyba nie. Pozwala to na bardzo krótkie rozwiązania w językach Ruby, Perl, PCRE i .NET.

Charles

2

rekurencja czyni z niej gramatykę bezkontekstową (jeśli może zdecydować {a*b*|a and b an equal amount of times})

maniak zapadkowy

@ratchet freak: Wiem, że technicznie nie jest to wyrażenie regularne, ale pytanie mówi, że każdy smak wyrażenia regularnego jest akceptowalny.

Lowjacker

Stworzyłem generator oparty na twoim poście, który tworzy je dla dowolnych dzielników i baz: github.com/ThePlasmaRailgun/DivisibilityRegexes . Ma również opcję generowania plików .jff dla JFLAP.

ThePlasmaRailgun

24

Byłem pod wrażeniem odpowiedzi Griffina i musiałem dowiedzieć się, jak to działa! Wynikiem jest następujący kod JavaScript. (To 3,5k znaków, co jest w pewnym sensie krótsze!) genFunkcja przyjmuje dzielnik i bazę i generuje wyrażenie regularne, które pasuje do liczb w określonej bazie, które są podzielne przez ten dzielnik.

Uogólniłem NFA Griffina dla dowolnej bazy: nfafunkcja przyjmuje dzielnik i bazę i zwraca dwuwymiarową tablicę przejść. Na przykład wejście wymagane do przejścia ze stanu 0 do stanu 2 to states[0][2] == "1".

reduceFunkcja przyjmuje w statestablicy i prowadzi go przez ten algorytm do przetłumaczenia NFA do wyrażenia regularnego. Wygenerowane wyrażenia regularne są ogromne i wyglądają, jakby zawierały wiele zbędnych klauzul, pomimo moich prób optymalizacji. Wyrażenie regularne dla 7 bazowych 10 ma około ~ 67k znaków; Firefox zgłasza „InternalError” dla n> 5 próbując parsować wyrażenie regularne; uruchamianie wyrażenia regularnego w Chrome zaczyna działać powoli dla n> 6.

Istnieje również testfunkcja, która pobiera wyrażenie regularne i bazowe i uruchamia go względem liczb od 0 do 100, więc test(gen(5)) == [0, 5, 10, 15, ...].

Pomimo nieoptymalnego wyniku, była to fantastyczna okazja do nauki i mam nadzieję, że część tego kodu będzie przydatna w przyszłości!

function gen(b, base) {
    var states = nfa(b, base)
    for (var i = 0; i < states.length; i++)
        states = reduce(states, i);
    return states[0][0] != 'phi' && new RegExp('^' + wrap(states[0][0]) + '$');
}

function test(reg, base) {
    if (!base)
        base = 10;

    var x = [];
    for (var i = 0; i < 100; i++)
        x.push(i);
    return x.map(function (a) {return a.toString(base)}).filter(reg.test.bind(reg)).map(function (a) {return parseInt(a, base)})
}

function nfa(b, base) {
    if (!base)
        base = 10;

    var states = [];
    for (var i = 0; i < b; i++) {
        states[i] = [];
        for (var j = 0; j < b; j++)
            states[i][j] = [];
    }

    for (var i = 0; i < b; i++)
        for (var n = 0; n < base; n++)
            states[i][(i * base + n) % b].push(n.toString());

    for (var i = 0; i < b; i++)
        for (var j = 0; j < b; j++)
            states[i][j] = states[i][j].length > 1 ? '[' + states[i][j].join('') + ']' : (states[i][j][0] || 'phi');
    return states;
}

// http://www.cs.umbc.edu/~squire/cs451_l7.html
function reduce(states, n) {
    var s = states.length;
    var reduced = [];
    for (var i = 0; i < s; i++) {
        reduced[i] = [];
        for (var j = 0; j < s; j++) {
            // reduced[i][j] = wrap(states[i][n] + wrap(states[n][n]) + '*' + states[n][j] + '|' + states[i][j]);
            reduced[i][j] = '';

            if (states[i][n] == 'phi' || states[n][j] == 'phi') {
                reduced[i][j] = states[i][j];
                continue;
            }

            if (states[i][n] != states[n][n])
                reduced[i][j] += wrap(states[i][n]);

            if (states[n][n] != 'phi') {
                reduced[i][j] += wrap(states[n][n]);

                if (states[i][n] == states[n][n] && states[n][j] == states[n][n])
                    reduced[i][j] += wrap(states[n][n]);

                if (states[i][n] == states[n][n] || states[n][j] == states[n][n])
                    reduced[i][j] += '+';
                else
                    reduced[i][j] += '*';
            }

            if (states[n][j] != states[n][n])
                reduced[i][j] += wrap(states[n][j]);

            reduced[i][j] = states[i][j] == 'phi' ? wrap(reduced[i][j]) : alternate(reduced[i][j], states[i][j]);
        }
    }
    return reduced;
}

function matching(x, open, close) {
    // Test if the parens are actually matching
    if ('(['.indexOf(x.charAt(open)) != -1 && ')]'.indexOf(x.charAt(close)) != -1) {
        var count = 0;
        for (var i = open; i <= close; i++) {
            if ('(['.indexOf(x.charAt(i)) != -1)
                count++;
            else if (')]'.indexOf(x.charAt(i)) != -1) {
                count--;

                if (count == 0)
                    return i == close;
            }
        }
    }

    return false;
}

function wrap(x) {
    if (x.length < 2 || matching(x, 0, x.length - 1))
        return x;
    return '(' + x + ')';
}

function optional(cond) {
    if (matching(cond, 0, cond.length - 2)) {
        var op = cond.charAt(cond.length - 1);
        if (op == '+')
            return cond.slice(0, -1) + '*';
        else if (op == '*' || op == '?')
            return cond;
    } else if (matching(cond, 0, cond.length - 1))
        return optional(cond.slice(1, -1));

    return wrap(cond) + '?';
}

function alternate(cond1, cond2) {
    cond2 = wrap(cond2);
    var index = cond1.indexOf(cond2);
    var len = cond2.length;
    var cond = '';

    if (index == 0) {
        var op = cond1.charAt(len);
        if (op == '*')
            cond = cond2 + '+' + optional(cond1.slice(len));
        else if (op == '+')
            cond = cond1;
        else 
            cond = cond2 + optional(cond1.slice(len));
    } else if (index == cond1.length - len)
        cond = optional(cond1.slice(0, index)) + cond2;
    else if (cond1.length == 1 && cond2.length == 1)
        cond = '[' + cond1 + cond2 + ']';
    else
        cond = cond1 + '|' + cond2;

    return wrap(cond);
}

Casey Chu
źródło

7

Perl / PCRE, 370 znaków

^(?!$|0.)([07]*(?:[18](?2)|[29](?3)|3(?4)|4(?5)|5(?7)|6(?9)|$))|(5*(?:[07](?4)|[18](?5)|[29](?7)|4(?1)|6(?3)|3(?9)))(3*(?:[18](?1)|[29](?2)|[07](?9)|4(?4)|5(?5)|6(?7)))([18]*(?:[07](?3)|[29](?5)|5(?1)|6(?2)|3(?7)|4(?9)))(6*([29](?1)|[07](?7)|[18](?9)|3(?2)|4(?3)|5(?4)))(4*([07](?2)|[18](?3)|[29](?4)|6(?1)|3(?5)|5(?9)))([29]*([07](?5)|[18](?7)|3(?1)|4(?2)|5(?3)|6(?4)))

Odrzuca pusty ciąg, a także ciągi z wiodącymi zerami (z wyjątkiem „0”).

Umorusany
źródło

@Charles To jest poprawne PHP PCRE i rzeczywiście działa, aby sprawdzić podzielność - spróbuj tutaj

cat

Hard code golf: Regex dla podzielności przez 7

Odpowiedzi:

10791 znaków, dozwolone zera wiodące

10795 znaków, zera wiodące zabronione

Wyjaśnienie

13 755 12 699 12 731 znaków

Jak się tam dostaniemy

Jak to działa

Więc uruchomienie testowe:

Dla liczb dziesiętnych

Rewizje

Wersja 5

Wersja 7

Wersja 10 i 11 (autor: nhahtdh)

Wyrażenie regularne .NET, 119 118 105 bajtów

Objaśnienie (poprzedniej wersji)

468 znaków

Perl / PCRE, 370 znaków