[Question]
  [
Given a [POSIX](http://en.wikipedia.org/wiki/Regular_expression#POSIX_basic_and_extended) [Extended Regular Expression](http://en.wikipedia.org/wiki/Regular_expression#POSIX_extended) 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](http://chat.stackexchange.com/transcript/message/14223416#14223416)):
```
^(([helo]([world][helo])*)?$|([helo][world])*[^helo]|[helo]([world][helo])*[^wo‌​rld])
```
Please post a few sample Input/Outputs
  
[Answer]
# 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!](https://tio.run/##XVRNb@M2EP0rMWEYw5jh2gl6qAraKPbUAm2AzZFmYFWmP7a0ZJBMNoHl354@UnLsrXSQOJw3b97MkN/L1zJUfneId3Wzsh@vpb/Z/lY1dWicla7ZEH3s1Wz5PDwSOVGrYyiO2pLTE8NNwdjpxNWMKKqgZrV@U5YCNwp/pm0pfdTxJLz0dvVSWSLyohFVglTK6XsDb2q4iFRx4TO8Apx8xjNtGNdDQxNxN@VjYosFU6rBhknfeVojBT5uxrAIp6cpHni9tAp24TkXxxPnvMtX0EY9/vPdVlH@a9/BXHO9NURWzVhgA2VHI6RVa2vESlX5Y52N9ub6P29vzlAHJQEQZ2DmA4iVb6PRp2s2j0YbqDozUaPCmFbzJQ2PqxO/XWYFmaH3P4fromXH3nJqh8fmxJdFw/tH1DJI25eKE5UKFFYpZceMze1cTwQMU6wFUo1qpiP@59PiXuA1CGuKzmdgRYbOprBQUgPnSUINXNs6GZq9zXptKrNL3Ajn1cyh@22rLSpsuFy7Mv5VHrJn6mfqsePkuZBSZugbn3fOhQaAc5N4Yenrk7YQG/AzJ@Yu8rQRzSd1J8ZlEPZ93vemZ4s5LESImGVkPpHZc/i5jucEsmhs9FxYxeyWSCAuXFT4hMR8CUf6Wss5VBLoYTwLiQlkEwLJcDC5XND/tSNz7@rKvaxsQOI/tcZ0hSLbhy3TKNM691g6W2/idm4vZwtBk9p7AeEu1TaNFu31ULHgdpVlhqbpJMlwcLtIX2ixkK1@XiwM/4LO7Vy0vusB54j6an2wWP759Pi3DNHv6s1u/S62iu3LA46bSoIgurY/bp5spNwNQFMtfaQ88Rl7KBEolTN5/@59@U6//sK7QvVJP@Xwcu2b/ddt6b/iLiI3frhPM65fFOs0ftttthEqDirBRBQh9X00OqJYReyywUa6MiDTCCZZ4c5m/SA8usBus81KXHJVGUmjJ9rKQ3MgNAmXBNNXoM@iPgg799c1GrhL29K0FA7TUSv2jKsp6Hg3NSLkQqM1QboyxD/qlX17XBPuKo69rn/5fkNX6rZNp51fjkEnIk8y4zkl2mFuJsiQrjMM@gUVERqp66nYXcYBUwAPZ/LpwczFucaU9sZCd/BoujXA6Tgm@nUaV8HaK5KpOenQ14h44sJzGi4/OLFn0lvrGqN/NN6tUISfl7dDXEwf/wE "JavaScript (Node.js) – 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])*)$
```
]