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!
Regular expressions: Finding negation of regular expression?
fl.formal languages;regular expressions
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).  Wouter Gelade, Frank Neven: Succinctness of the Complement and Intersection of Regular Expressions. STACS 2008: 325-336Hermann Gruber, Markus Holzer: Finite Automata, Digraph Connectivity, and Regular Expression Size. ICALP (2) 2008: 39-50