# Complement of a Regex

For the purposes of this challenge, we define a postfix regex dialect with alphabet {1, 0} and the following operations:

• 1 and 0 match themselves literally.
• _ matches the empty string.
• ! always fails (i.e. it does not match anything).
• ab; matches a, followed by b.
• ab| matches both a and b.
• a+ matches one or more instances of a.

The regex should always start matching from the start of the string, and stop matching at the end of a string (in other word, it is implicitly wrapped in ^\$).

As an example, the following regex matches any string with an even number of 1s:

0+_|10+_|;10+_|;;+_|;


This is equivalent to the regex 0*(10*10*)*.

The following regex matches any nonempty string of ASCII letters, expressed in binary:

110|010|10|10|10|;;;;1010|10|10|;;;10010|;10;|;;|;|;;+


This is equivalent to the regex (1.(0....|1(0...|10(0.|10))))* (where . matches any character.

You can test regexes with this program.

## The Challenge

Given a regex in the format described above, return a regex in this format that matches precisely those strings that are not matched by the input.

One potential method to do this would be to convert the regex into a nondeterministic finite automaton, then convert that into a deterministic finite automaton, flip which states are designated as accept states, and then convert it back to a regex.

## Test Cases

format:
input   => potential output
equivalent infix regex

0       => _101|+_|;|
|1.*
1       => _001|+_|;|
|0.*
_       => 01|+
.+
!       => 01|+_|
.*
01|+    => _

01|+_|  => !
[] (empty character class)
1001;;; => _01|01|01|;01|01|01|;;001|01|01|01|+_|;;;;01|101|01|01|+_|;;;;01|01|101|01|+_|;;;;01|01|01|001|+_|;;;;|||||||
|.|..|...|0....*|.1...*|..1..*|...0.*

• But /0*(10*)*/ is not an regex for matching any string with an even number. – tsh Apr 3 '18 at 6:50
• That regex should probably have been 0*(10*10*)*. – Martin Ender Apr 3 '18 at 7:17
• Your first two test cases seem wrong. The outputs should also match strings which aren't of length 1. – Martin Ender Apr 3 '18 at 7:18
• Related – Martin Ender Apr 3 '18 at 7:27
• How should a regex that contains ! behave? Always fail? – Erik the Outgolfer Apr 3 '18 at 11:41