35
\$\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

Improve this question
\$\endgroup\$
27
  • 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, 2014 at 3:51
  • 4
    \$\begingroup\$ As far as I can see, there is no way to complement the empty pattern that matches everything. \$\endgroup\$
    – Heiko Oberdiek
    Mar 17, 2014 at 4:33
  • 23
    \$\begingroup\$ Oh "complement", not "compliment"... I was going to answer something on the lines of "Nice word boundaries!" \$\endgroup\$
    – Eliseo D'Annunzio
    Mar 17, 2014 at 10:41
  • 6
    \$\begingroup\$ I'd suggest a simple grammar that can be described in a few lines. You could use the formal definition of a regular expression, which only uses concatenation (RS), alternation (R|S), and Kleene star (R*). \$\endgroup\$
    – Peter Olson
    Mar 17, 2014 at 19:06
  • 10
    \$\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, 2014 at 14:33

1 Answer 1

Reset to default
21
+1000
\$\begingroup\$

JavaScript, 1563 bytes

m=>`^${((l,n={s:{[e(l[0])]:""}})=>((t=s=>n[x=e(s)]=n[x]||(n[x]={},r.reduce(((r,o,c)=>(c=l[2](s)(o),t(c),r[x=e(c)]=(r[x]||"[]")[$](0,-1)+("\\"==o||"]"==o?"\\":"")+o+"]",l[1](s)||(r.e=""),r)),{})))(l[0]),(g=Object.keys)(n)[h]((e=>"s"!=e&&(c=n[e],d=c[e],delete c[e],delete n[e],g(n)[h]((l=>(s=n[l][e])!={}.x&&delete n[l][e]&&g(c)[h]((e=>(o=s+(d?`(${d})*`:"")+c[e],n[l][e]=n[l][e]!={}.x?`(${n[l][e]}|${o})`:o)))))))),n.s.e||"[]"))((a=e=>e===e+""?e?[0,e=>1==e,l=>t=>[t==e?1:2,2,2][l]]:[0,e=>!e,e=>e=>1]:[([e])=>[0,l=>!l||l.some((l=>e[1](l))),t=>r=>l((t||[e[0]]).flatMap((l=>[x=e[2](l)(r),...e[1](x)?[e[0]]:[]])))],e=>[e[h]((e=>e[0])),l=>l.some(((l,t)=>e[t][1](l))),l=>t=>l[h](((l,r)=>e[r][2](l)(t)))],([e,t])=>[[e[0],e[1](e[0])?[t[0]]:[]],e=>e[1].some((e=>t[1](e))),r=>s=>[x=e[2](r[0])(s),l([...e[1](x)?[t[0]]:[],...r[1][h]((e=>t[2](e)(s)))])]],l=>[0,e=>1==e,l=>t=>[e[1].includes(t)?1:2,2,2][l]]][e[0]](e[1][h](a)))((f=e=>e.length?e.reduce(((e,l)=>[2,[e,l]])):"")(m[$="slice"](1,-1).split(/(\\.|[^\\])/).filter((e=>e)).reverse(e=JSON.stringify,l=l=>[...new Set(l[h](e))].sort()[h](JSON.parse),r=[...Array(95)][h](((e,l)=>String.fromCharCode(l+32))),h="map")[u="reduceRight"](p=(e,l,t,s)=>e&&{[l]:t=>[...e,l[$](-1)],".":l=>[...e,[3,r]],"*":l=>e.concat([[0,[e.pop()]]]),"[":l=>[...e,((e,l)=>[3,e?r.filter((e=>!l.includes(e))):l])(n="^"==s[t-1],s.splice(s.lastIndexOf("]"),s.length)[$](1,-n||{}.x)[h]((e=>e[$](-1))))],")":l=>(i=e,0),"(":l=>[...e,(s[u](p,[]),[1,i.reduce((([e,...l],t)=>1==t?[[],e,...l]:[[...e,t],...l]),[[]])[h](f)])],"|":l=>[...e,1]}[s.pop()](),[]))))}$`

Try it online!

Input/Output Examples

The challenge was to golf the source, not the output ¯\_(ツ)_/¯

Input: ^([helo][world])([helo][world])*$
Output: ^(((((((((|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo])|[ehlo][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ehlo])|[ehlo][dlorw][ehlo][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ehlo][dlorw][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ehlo][dlorw][ehlo](|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*))|[ehlo][dlorw][ehlo][dlorw][ehlo][dlorw]([ehlo][dlorw])*([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*|[ehlo](|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)))$

Input: ^.*$
Output: ^[]$ # Empty character set matches nothing

Input: ^[]$
Output: ^(|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)$

Input: ^(|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)$
Output: ^[]$

Ungolfed Less Golfed

let input = "^([helo][world])([helo][world])*$"

const star = 0
const union = 1
const concat = 2
const group = 3
const charset = [...Array(95)].map((_, i) => String.fromCharCode(i + 32));

input = `.*${input}.*`.replace(/\.\*\^|\$\.\*/g, "");

const makeConcat = x => x.length ? x.reduce((a, b) => [concat, [a, b]]) : "";

const regex = makeConcat(input
  .split(/(\\.|[^\\])/)
  .filter(x => x)
  .reverse()
  .reduceRight(_parseRegex = (acc, char, i, arr) => (
    acc && {
      [char]: _ => [...acc, char.slice(-1)],
      ".": _ => [...acc, [group, charset]],
      "*": _ => acc.concat([[star, [acc.pop()]]]),
      "[": _ => [...acc, ((i, a) =>
        [group, i ? charset.filter(x => !a.includes(x)) : a]
      )(
        invert = arr[i - 1] == "^",
        arr
          .splice(arr.lastIndexOf("]"), arr.length)
          .slice(1, -invert || {}.x)
          .map(x => x.slice(-1))
      )],
      ")": _ => (result = acc, null),
      "(": _ => [...acc, (
        arr.reduceRight(_parseRegex, []),
        [union, result.reduce(([a, ...b], char) => (
          char == union ? [[], a, ...b] : [[...a, char], ...b]
        ), [[]]).map(makeConcat)]
      )],
      "|": _ => [...acc, union],
    }[arr.pop()]()
  ), []))

const str = JSON.stringify;
const set = x => [...new Set(x.map(str))].sort().map(JSON.parse)

const initial = 0;
const accept = 1;
const next = 2;

const dfa = (regexToDfa = re =>
  re === re + ""
    ? re
      ? [0, x => x == 1, x => c => [c == re ? 1 : 2, 2, 2][x]]
      : [0, x => !x, x => c => 1]
    : [
      // star
      ([sub]) => [
        0,
        state => !state || state.some(substate => sub[accept](substate)),
        state => char => set((state || [sub[initial]]).flatMap(substate => [
          x = sub[next](substate)(char),
          ...sub[accept](x) ? [sub[initial]] : []
        ]))
      ],
      // union
      subs => [
        subs.map(sub => sub[initial]),
        state => state.some((substate, i) => subs[i][accept](substate)),
        state => char => state.map((substate, i) => subs[i][next](substate)(char)),
      ],
      // concat
      ([a, b]) => [
        [a[initial], a[accept](a[initial]) ? [b[initial]] : []],
        state => state[1].some(x => b[accept](x)),
        state => char =>
          [
            x = a[next](state[0])(char),
            set([
              ...a[accept](x) ? [b[initial]] : [],
              ...state[1].map(substate => b[next](substate)(char))
            ])
          ]
      ],
      // group
      _ => [
        0,
        state => state === 1,
        state => char => [re[1].includes(char) ? 1 : 2, 2, 2][state],
      ]
    ][re[0]](re[1].map(regexToDfa))
)(regex)

const testDfa = i => dfa[accept]([...i].reduce((a, b) => dfa[next](a)(b), dfa[initial]))

const invertDfa = dfa => [dfa[initial], x => !dfa[accept](x), dfa[next]]

const dfaToString = (dfa, paths = { s: { [str(dfa[initial])]: "" } }) =>
(
  (visitState = (state) => paths[x = str(state)] = paths[x] || (paths[x] = {},
    charset.reduce((obj, char, nextState) => (
      nextState = dfa[next](state)(char),
      visitState(nextState),
      obj[x = str(nextState)] = (obj[x] || "[]").slice(0, -1) + (char == "\\" || char == "]" ? "\\" : "") + char + "]",
      dfa[accept](state) && (obj.e = ""),
      obj
    ), {})
  ))(dfa[initial]),
  Object.keys(paths).map(removeState => removeState != "s" && (
    obj = paths[removeState],
    selfPath = obj[removeState],
    delete obj[removeState],
    delete paths[removeState],
    Object.keys(paths).map(a => (
      initialPath = paths[a][removeState]) !== {}.x &&
      delete paths[a][removeState] &&
      Object.keys(obj).map(b => (
        path = initialPath + (selfPath ? `(${selfPath})*` : "") + obj[b],
        paths[a][b] = paths[a][b] != {}.x ? `(${paths[a][b]}|${path})` : path
      ))
    )
  )),
  paths.s.e || "[]"
)

console.log(`^${dfaToString(invertDfa(dfa))}$`)

Explanation

The program executes the following process:

  1. Parse the regex into a tree structure
  2. Convert the tree structure into a DFA
  3. Invert the accepted/rejected states of the DFA
  4. Convert the DFA into a (stringified) regex

In the parsed regex tree, the leaves are characters, and the branches are operations. For example, ^a[bc](d|e*)$ would look like

[2 /* concat */, [
  [2 /* concat */, [
    "a",
    [3 /* character group */, [
      "b",
      "c",
    ]],
  ]],
  [1 /* union */, [
    "d",
    [0 /* star */, [
      "e",
    ]],
  ]],
]]

A DFA is represented as a 3-tuple:

[
  initial /* state */,
  accept /* state => bool */,
  next /* state => char => bool */,
]

States are numbers or deep arrays of numbers.

To convert this parsed regex into a DFA, the tree is processed bottom-up. Single characters and character groups become 3-state DFAs (start, accept, and dead). Operations compose their DFA operands in various ways; for example, union tracks the state of each operand, and accepts any state where one of the operands is accepting.

The DFA is then inverted by negating the accept function.

To convert the inverted DFA into a regex, it is encoded into a JS object that represents a (state, state) -> string. Each string will be a regex that accepts the set of strings that will move the DFA from one state to another. Initially, the strings are simply character classes containing all of the characters between the two states in the DFA. This is what the object would look like initially for the regex ^[ab]$, if the alphabet was limited to abc.

{
  s: { 0: "" },
  0: { 1: "[ab]", 2: "[c]" },
  1: { e: "", 2: "[abc]" },
  2: { 2: "[abc]" },
}

The special keys s and e represent the start and end, respectively. In this case, the state 2 is a dead state, where no progress can be made. The leaf values are referred to "arrows"; for example, the 01 arrow goes from 0 to 1 and has a regex of [ab]. Any non-existent arrows have a regex of [], a regex that matches nothing.

This object now needs to be distilled to a singular regex. Then, each of the states is removed iteratively. When removing states, the arrows associated with those states must be combined with the other regexes.

If there are states A and B (not necessarily distinct), and a state X which is being removed, arrow AB will be upserted to be

<AB>|<AX><XX>*<XB>

Note that:

  • If there is no XX arrow, the AB arrow will become <AB>|<AX><XB>, as []* is equivalent to () (the regex that matches the empty string).
  • If there is no AB arrow, there will be a new arrow that is <AX><XX>*<XB>.
  • If there is no AX arrow or no XB arrow, the AB arrow will be unchanged.

Thus, the object evolves as follows:

// Original
{
  s: { 0: "" },
  0: { 1: "[ab]", 2: "[c]" },
  1: { e: "", 2: "[abc]" },
  2: { 2: "[abc]" },
}

// After removing 0
{
  s: { 1: "[ab]", 2: "[c]" },
  1: { e: "", 2: "[abc]" },
  2: { 2: "[abc]" },
}

// After removing 0 and 1
{
  s: { e: "[ab]", 2: "[c]|[ab][abc]" },
  2: { 2: "[abc]" },
}

// Final
{
  s: { e: "[ab]" },
}

In the end, the object will be { s: { e: <regex> } } or { s: {} }. If it's the latter, there was no path from s to e, so the final regex is [].

Interestingly, this process is far from lossless; running a regex through without inverting it often still explodes the size:

Input: ^a[bc](d|e*)$
Output (not inverted): ^((([a][bc]|[a][bc][d])|[a][bc][e])|[a][bc][e][e]([e])*)$
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.