5 ms·

This "walk on a graph" is known formally as a Deterministic Finite Automata. One of the interesting results of automata theory is that every FA has an equivalen

by sirsar 11y ago

This "walk on a graph" is known formally as a Deterministic Finite Automata. One of the interesting results of automata theory is that every FA has an equivalent regular expression (a subset of the "regexps" in most modern programming languages). Where is this going? Behold, a 12,701 character regex for divisibility by 7: http://codegolf.stackexchange.com/questions/3503/hard-code-golf-regex-for-divisibility-by-7 http://codegolf.stackexchange.com/questions/3503/hard-code-g... This doesn't use any recursive features (it is a real Regular Expression in the theoretic sense) so it can be checked in linear time.

raverbashing 11y ago
The weird part is that the regex is much bigger than the DFA (but the DFA is not accepting the symbols directly, it's transforming them first It also seems that regexes can't express accepting expressions like AB where A is accepted by itself (considering AB is accepted), which in the DFA is implemented by sending it to the initial state
- robryk 11y ago
  > It also seems that regexes can't express accepting expressions like AB where A is accepted by itself (considering AB is accepted), which in the DFA is implemented by sending it to the initial state B* does that.
newsignup 11y ago
> a 12,701 character regex for divisibility by 7: I wonder if that's the optimal regex or can be reduced further using some rules[1] like the ones which we(humans) generally use to do it manually. [1]. https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml
- ant6n 11y ago
  Don't regular expressions have minimal, canonical forms?
  - Ar-Curunir 11y ago
    Yes they do. For reference, check Sipser.
    - sirsar 11y ago
      Could you give a page number? I skimmed the regular expression section and couldn't find it. Also, while it is self-evident to me that there is a minimal form for each regex, the construction for finding one isn't immediately obvious to me (I can surely enumerate several ways of eliminating redundancy). Beyond that, I'm not sure a minimal form would minimize character length. Of (a \star b \star ) \star and ( a ∪ b ) \star, which is the canonical form? The transformation from the former to the latter is nontrivial as a \star b \star is not equivalent with a ∪ b.
      - areyousure 11y ago
        Of course, there is a shortest equivalent regular expression, but in general it's PSPACE-complete to find it: https://en.wikipedia.org/wiki/PSPACE-complete#Regular_expressions https://en.wikipedia.org/wiki/PSPACE-complete#Regular_expres... It remains PSPACE-complete if you're given a corresponding DFA: "Jiang and Ravikumar [7] show moreover that the minimization problem for ... regular expressions remains PSPACE-complete, even when specifying the regular language by a dfa" from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.5056&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.... In that sense, the grandparent is incorrect. It is unknown, in both practice and theory, how to find the shortest equivalent regex.
        adrianN 11y ago
        It's not unknown, it just takes a long time.
        acchow 11y ago
        I think you should think deeper on the idea of "unknown"
- eru 11y ago
  It's definitely not the optimal regex. Finding the smallest regex is a hard problem (at least in theory): https://cs.stackexchange.com/questions/19686/is-regex-golf-np-complete https://cs.stackexchange.com/questions/19686/is-regex-golf-n... (I think I've read that finding the smallest one is not only NP-hard, but P-Space complete.)
- anderskaseorg 11y ago
  I wrote a 11811-character regex for divisibility by 7 back in August 2008: http://web.mit.edu/andersk/Public/regex http://web.mit.edu/andersk/Public/regex
  - eru 11y ago
    Do you have the source to the program you wrote the regex with? (Or did you write it by hand?)
  - fizbin 11y ago
    And unlike the one on stackexchange, it's actually correct! (I have a regex -> DFA compiler here that I just threw your regex through. Seven states, connected as expected)
anewhnaccount 11y ago
This is a DFA over the alphabet {0, 1} where the number is first transformed by writing out each digit in unary with 1 and delimiting digits with 0.
eru 11y ago
Wow, I'm famous.
fizbin 11y ago
Note that the 12,701 character regex is WRONG. It doesn't even match "70". Even the binary regex is wrong. The original 32K regex pointed to in the stackexchange problem statement however is perfectly correct. Test code: open(F, '< /tmp/q.in'); $myre = <F>; chomp($myre); $myrecomp = qr/^(?:$myre)$/; while (<>) { chomp(); if (m/$myrecomp/) { print "$_\n"; } } Examples of multiples of 7 not matched by the given regex: 70, 707, 7007, 11095 (I spent all morning trying to find the bug in my regex compiler based on the assumption that the answer there was correct)

by sirsar 11y ago

raverbashing 11y ago

The weird part is that the regex is much bigger than the DFA (but the DFA is not accepting the symbols directly, it's transforming them first It also seems that regexes can't express accepting expressions like AB where A is accepted by itself (considering AB is accepted), which in the DFA is implemented by sending it to the initial state

robryk 11y ago
> It also seems that regexes can't express accepting expressions like AB where A is accepted by itself (considering AB is accepted), which in the DFA is implemented by sending it to the initial state B* does that.

newsignup 11y ago

> a 12,701 character regex for divisibility by 7: I wonder if that's the optimal regex or can be reduced further using some rules[1] like the ones which we(humans) generally use to do it manually. [1]. https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml https://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml

ant6n 11y ago
Don't regular expressions have minimal, canonical forms?
- Ar-Curunir 11y ago
  Yes they do. For reference, check Sipser.
  - sirsar 11y ago
    Could you give a page number? I skimmed the regular expression section and couldn't find it. Also, while it is self-evident to me that there is a minimal form for each regex, the construction for finding one isn't immediately obvious to me (I can surely enumerate several ways of eliminating redundancy). Beyond that, I'm not sure a minimal form would minimize character length. Of (a \star b \star ) \star and ( a ∪ b ) \star, which is the canonical form? The transformation from the former to the latter is nontrivial as a \star b \star is not equivalent with a ∪ b.
    - areyousure 11y ago
      Of course, there is a shortest equivalent regular expression, but in general it's PSPACE-complete to find it: https://en.wikipedia.org/wiki/PSPACE-complete#Regular_expressions https://en.wikipedia.org/wiki/PSPACE-complete#Regular_expres... It remains PSPACE-complete if you're given a corresponding DFA: "Jiang and Ravikumar [7] show moreover that the minimization problem for ... regular expressions remains PSPACE-complete, even when specifying the regular language by a dfa" from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.5056&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.... In that sense, the grandparent is incorrect. It is unknown, in both practice and theory, how to find the shortest equivalent regex.
      - adrianN 11y ago
        It's not unknown, it just takes a long time.
        acchow 11y ago
        I think you should think deeper on the idea of "unknown"
eru 11y ago
It's definitely not the optimal regex. Finding the smallest regex is a hard problem (at least in theory): https://cs.stackexchange.com/questions/19686/is-regex-golf-np-complete https://cs.stackexchange.com/questions/19686/is-regex-golf-n... (I think I've read that finding the smallest one is not only NP-hard, but P-Space complete.)
anderskaseorg 11y ago
I wrote a 11811-character regex for divisibility by 7 back in August 2008: http://web.mit.edu/andersk/Public/regex http://web.mit.edu/andersk/Public/regex
- eru 11y ago
  Do you have the source to the program you wrote the regex with? (Or did you write it by hand?)
- fizbin 11y ago
  And unlike the one on stackexchange, it's actually correct! (I have a regex -> DFA compiler here that I just threw your regex through. Seven states, connected as expected)

anewhnaccount 11y ago

This is a DFA over the alphabet {0, 1} where the number is first transformed by writing out each digit in unary with 1 and delimiting digits with 0.

eru 11y ago

Wow, I'm famous.

fizbin 11y ago

Note that the 12,701 character regex is WRONG. It doesn't even match "70". Even the binary regex is wrong. The original 32K regex pointed to in the stackexchange problem statement however is perfectly correct. Test code: open(F, '< /tmp/q.in'); $myre = <F>; chomp($myre); $myrecomp = qr/^(?:$myre)$/; while (<>) { chomp(); if (m/$myrecomp/) { print "$_\n"; } } Examples of multiples of 7 not matched by the given regex: 70, 707, 7007, 11095 (I spent all morning trying to find the bug in my regex compiler based on the assumption that the answer there was correct)