18
\$\begingroup\$

Given a POSIX Extended Regular Expression as input, output its complement (also a POSIX ERE). If the given regular expression matches a string, its complement should not match it, and the regex: (regex given)|(complement) should match any string. In other words, negate the regex.

The regex for format input and for output, POSIX ERE, is basically regex without character classes, lookarounds, backreferences, etc. You can assume that we only care about ASCII characters. Also, assume that character classes do not contain - for use as ranges (no [a-d] as input; instead, the input would be [abcd]). Further assume that ? and + and {} will not be used in the input as metacharacters. x? will be shown with x| and x+ by xx* where x is an arbitrary regular expression. The variations of {m,n} will be similarly written out (e.g.: instead of x{1,4}, you'll get x|xx|xxx|xxxx).

Sample Input:

^([helo][world])([helo][world])*$

Possible Output (Thanks Peter Taylor):

^(([helo]([world][helo])*)?$|([helo][world])*[^helo]|[helo]([world][helo])*[^wo‌​rld])

Please post a few sample Input/Outputs

\$\endgroup\$
  • 2
    \$\begingroup\$ The string ao is neither matched by the input nor the given output. A possible output would be ^(|(..)*.|(..)*[^helo].(..)*|(..)*.[^world](..)*)$ (assuming . matches all characters). \$\endgroup\$ – Heiko Oberdiek Mar 17 '14 at 3:51
  • 2
    \$\begingroup\$ As far as I can see, there is no way to complement the empty pattern that matches everything. \$\endgroup\$ – Heiko Oberdiek Mar 17 '14 at 4:33
  • 15
    \$\begingroup\$ Oh "complement", not "compliment"... I was going to answer something on the lines of "Nice word boundaries!" \$\endgroup\$ – WallyWest Mar 17 '14 at 10:41
  • 3
    \$\begingroup\$ Hmm had more of a look at this. It's possible, but crazy tedious. You need to parse the regexp into an NFA (eg Thompson's algorithm), convert the NFA to a DFA (powerset construction), complete the DFA, find the complement, then convert the DFA to a RE (eg Brzozowski's method). ie slightly harder than writing a complete RE engine! I'd expect a golfed version would need to use library functions for each step. \$\endgroup\$ – bazzargh Apr 1 '14 at 14:33
  • 3
    \$\begingroup\$ Your sample input uses +, but you state that + will not be used \$\endgroup\$ – Mego Oct 4 '16 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.