Mon, 17 May 2010 11:19:11 +0200

Related articles |
---|

NFA and negation/conjunction monnier@iro.umontreal.ca (Stefan Monnier) (2010-05-13) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-14) |

Re: NFA and negation/conjunction sh006d3592@blueyonder.co.uk (Stephen Horne) (2010-05-15) |

Re: NFA and negation/conjunction monnier@iro.umontreal.ca (Stefan Monnier) (2010-05-15) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-16) |

Re: NFA and negation/conjunction cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-16) |

Re: NFA and negation/conjunction torbenm@diku.dk (2010-05-17) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-19) |

Re: NFA and negation/conjunction rsc@swtch.com (Russ Cox) (2010-05-19) |

Re: NFA and negation/conjunction torbenm@diku.dk (2010-05-20) |

From: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | Mon, 17 May 2010 11:19:11 +0200 |

Organization: | UNI-C |

References: | 10-05-078 |

Keywords: | lex |

Posted-Date: | 19 May 2010 00:32:16 EDT |

Stefan Monnier <monnier@iro.umontreal.ca> writes:

*> I'm looking for any work that tries to provide negation and/or*

*> conjunction operations in regexps without using a DFA (or at least*

*> while avoiding the DFA state explosion problem).*

I assume you mean intersection when you say conjunctipon.

*> My search has currently come up empty (actually I pretty much haven't*

*> seen mention of conjunction and negation in regexps other than in*

*> Brzozowski's derivatives). So any pointer would be welcome,*

You can do intersection of epsilon-free NFAs using the construction

that you use for DFAs (constructing a product automaton). If you just

do a single intersection, this stays quadratic, but multiple

intersections gets exponential. This can't be avoided, as deciding

emptyness of the intersection of a set of regexps is PSPACE complete

in the combined size of the regexps. Since deciding emptyness is

linear in teh size of an automaton, you can't construct an automaton

faster.

Complement of complete DFAs (i.e., DFAs without undefined transitions)

is trivial: You just negate the accepting-state bit. If your DFA is not

complete, it is easy to make it so (just add a dead state and make all

undefined transitions go to this). But I don't think there is a

sub-exponential complement construction for regexps or NFAs.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.