5
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – mhum
    Feb 24, 2011 at 16:44
  • $\begingroup$ 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? $\endgroup$
    – Simon
    Feb 24, 2011 at 16:46
  • 1
    $\begingroup$ 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 $\endgroup$
    – Dave Clarke
    Feb 24, 2011 at 16:54
  • 2
    $\begingroup$ 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? $\endgroup$
    – Jukka Suomela
    Feb 24, 2011 at 19:08
  • 3
    $\begingroup$ meta-discussion here: meta.cstheory.stackexchange.com/questions/1015/… $\endgroup$
    – Suresh Venkat
    Feb 24, 2011 at 20:25

1 Answer 1

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Very interesting references! $\endgroup$
    – mhum
    Feb 24, 2011 at 21:14
  • 4
    $\begingroup$ 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. $\endgroup$
    – mikero
    Feb 25, 2011 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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