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

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

<ul>
<li>Wouter Gelade, Frank Neven: <a href="http://drops.dagstuhl.de/opus/volltexte/2008/1354/pdf/22011.GeladeWouter.Paper.1354.pdf">Succinctness of the Complement and Intersection of Regular Expressions</a>. STACS 2008: 325-336</li>
<li>Hermann Gruber, Markus Holzer: <a href="http://www.hermann-gruber.com/data/icalp08.pdf">Finite Automata, Digraph Connectivity, and Regular Expression Size.</a> ICALP (2) 2008: 39-50</li>
</ul>

CC BY-SA 2.5
2011-02-24T21:14:44.877Z
Very interesting references!
mhum
CC BY-SA 2.5
2011-02-25T14:52:11.560Z
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](http://portal.acm.org/citation.cfm?id=804029) (STOC 73) for this and many other interesting decision problems for regular expression variants.
mikero
CC BY-SA 2.5
2011-02-24T19:25:37.363Z
2011-02-24T19:25:37.363Z
Hermann Gruber
<p>Given regular expressions containing <em>only</em> <code>(,),|,*</code> and characters of an Alphabet A, how can I find the "negation" of a regular expression i.e.:</p>

<ul>
<li><code>&lt;R1&gt; is a regular expression</code></li>
<li><code>&lt;R2&gt; = A*\&lt;R1&gt;</code></li>
</ul>

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

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

<p>Thank you!</p>

CC BY-SA 2.5
2011-02-24T16:44:47.453Z
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
CC BY-SA 2.5
2011-02-24T16:46:52.057Z
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
CC BY-SA 2.5
2011-02-24T16:54:47.203Z
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]: http://portal.acm.org/citation.cfm?id=321249
Dave Clarke
CC BY-SA 2.5
2011-02-24T17:51:18.880Z
@Simon why "human"? Is there a Turing test before actual CS test? Just kidding best of luck! :)
Pratik Deoghare
CC BY-SA 2.5
2011-02-24T19:08:58.653Z
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
CC BY-SA 2.5
2011-02-24T20:25:27.063Z
meta-discussion here: http://meta.cstheory.stackexchange.com/questions/1015/finding-negation-of-regular-expression-too-basic
Suresh Venkat
<fl.formal-languages><regular-expressions>
Regular expressions: Finding "negation" of regular expression?
Simon
# Regular expressions: Finding "negation" of regular expression?

(Asked by: username_0 on 2011-02-24)

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

* `is a regular expression`
* `= A*\`

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

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

Thank you!

**Tags:** fl.formal-languages, regular-expressions

> **Comments:**
> **username_1**: 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.  
> **username_0**: I agree with username_1. I will write a CS test on tuesday. How can I quickly find R2? Is there any "human" way of seeing what to do?  
> **username_2**: 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]: http://portal.acm.org/citation.cfm?id=321249  
> **username_3**: @username_0 why "human"? Is there a Turing test before actual CS test? Just kidding best of luck! :)  
> **username_4**: 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?  
> **username_5**: meta-discussion here: http://meta.cstheory.stackexchange.com/questions/1015/finding-negation-of-regular-expression-too-basic  

---

## 1 answers

### Answer by username_6 on 2011-02-24. Score: 13 | Accepted 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).

* Wouter Gelade, Frank Neven: [Succinctness of the Complement and Intersection of Regular Expressions](http://drops.dagstuhl.de/opus/volltexte/2008/1354/pdf/22011.GeladeWouter.Paper.1354.pdf). STACS 2008: 325-336
* username_6, Markus Holzer: [Finite Automata, Digraph Connectivity, and Regular Expression Size.](http://www.hermann-gruber.com/data/icalp08.pdf) ICALP (2) 2008: 39-50

> **Comments:**
> **username_1**: Very interesting references!  
> **username_7**: 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](http://portal.acm.org/citation.cfm?id=804029) (STOC 73) for this and many other interesting decision problems for regular expression variants.  

---

