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


&lt;R1&gt; is a regular expression
&lt;R2&gt; = A*\&lt;R1&gt;


where A* are all the words you can produce with A and &lt;Ri&gt; the words accepted by the regular expression Ri. 

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

Thank you!
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 &amp; Neven 2008, and Gruber &amp; Holzer 2008).  


Wouter Gelade, Frank Neven: Succinctness of the Complement and Intersection of Regular Expressions. STACS 2008: 325-336
Hermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50