Search code examples
regexcomputation-theory

Negation of a regular expression

I am not sure how it is called: negation, complementary or inversion. The concept is this. For example having alphabet "ab"

R = 'a'
!R = the regexp that matche everyhting exept what R matches

In this simple example it should be soemthing like

!R = 'b*|[ab][ab]+'

How is such a regexp called? I remeber from my studies that there is a way to calculate that, but it is something complicated and generally too hard to make by hand. Is there a nice online tool (or regular software) to do that?

Solution

  • jbo5112's answer gives good practical help. However, on the theoretical side: a regular expression corresponds to a regular language, so the term you're looking for is complementation.

    To complement a regex:

    1. Convert into the equivalent NFA. This is a well-known and defined process.
    2. Convert the NFA to a DFA via the powerset construction
    3. Complement the DFA by making accept states not accept and vice versa.
    4. Convert the DFA to a regular expression.

    You now have the complement of the original regular expression!