# Regular expressions: Finding “negation” of regular expression?

Given regular expressions containing only (,),|,* and characters of an Alphabet A, how can I find the "negation" of a regular expression i.e.:

• <R1> is a regular expression
• <R2> = A*\<R1>

where A* are all the words you can produce with A and <Ri> the words accepted by the regular expression Ri.

Given R1, how can I find R2? Is there any algorithm to do that?

Thank you!

-
Indeed, this is the standard procedure. However, I've always wondered if there were convenient way to do this without passing through an NFA. I only bring this up because from a practical standpoint converting an NFA to a regular expression can sometimes be a hassle. –  mhum Feb 24 '11 at 16:44
I agree with mhum. I will write a CS test on tuesday. How can I quickly find R2? Is there any "human" way of seeing what to do? –  Simon Feb 24 '11 at 16:46
Straightforward: convert regular expression to a non-deterministic finite state automaton, determinize it, flip the final states (making non-final states final and vice versa), and then convert the resulting automaton to a regular expression. All of these constructions can be found in any good book on automata theory. A more direct approach is to convert the regular expression to a deterministic finite state automaton directly using [Brzozowski's derivative][1]. [1]: portal.acm.org/citation.cfm?id=321249 –  Dave Clarke Feb 24 '11 at 16:54
As pointed out by @Moron, this isn't really a research-level question, and hence off-topic here. But perhaps we could take this as a challenge: who can come up with a closely related question that is an intriguing research-level problem? –  Jukka Suomela Feb 24 '11 at 19:08
meta-discussion here: meta.cstheory.stackexchange.com/questions/1015/… –  Suresh Venkat Feb 24 '11 at 20:25

## 1 Answer

As another answer already states, the standard approach is: converting to a DFA, complementing, and converting back to a regular expression takes two exponential steps in the worst case (one for obtaining the equivalent DFA, and one for converting its complement to a regular expression).

This is essentially optimal in the worst case: There are examples of regular expressions of length $n$ such that the shortest regular expression describing complement provably has length at least $2^{2^{c \cdot n}}$, where $c$ is some fixed constant; Such examples are known already for alphabets of size $2$. (Gelade & Neven 2008, and Gruber & Holzer 2008).

-
Very interesting references! –  mhum Feb 24 '11 at 21:14
It is PSPACE-complete to determine whether a regular expression accepts ALL strings. Thus a special case of the original question is PSPACE-complete (determining whether the complement of a regular expression is empty). See Meyer & Stockmeyer Word Problems Requiring Exponential Time (STOC 73) for this and many other interesting decision problems for regular expression variants. –  mikero Feb 25 '11 at 14:52