# 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, 2011 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? Feb 24, 2011 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 Feb 24, 2011 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? Feb 24, 2011 at 19:08
• meta-discussion here: meta.cstheory.stackexchange.com/questions/1015/… Feb 24, 2011 at 20:25

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).