Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
1  
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
2  
meta-discussion here: meta.cstheory.stackexchange.com/questions/1015/… –  Suresh Venkat Feb 24 '11 at 20:25
show 1 more comment

1 Answer

up vote 11 down vote accepted

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

share|improve this answer
4  
Very interesting references! –  mhum Feb 24 '11 at 21:14
4  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.