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:


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

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


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

input   => potential output
           equivalent infix regex

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

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.