[clug] OT meta-regex question

[David Gibson]

On Tue, Feb 03, 2004 at 04:28:36PM +1100, David Price wrote:
> On Tue, Feb 03, 2004 at 02:24:22PM +1100, Gough, Chris wrote:
> > ...an off topic question, in search of guru guidance
> > 
> > I want a function that tells me if there exists a pattern (anywhere in the
> > universe strings) that will be matched by both of a pair a pair of regular
> > expressions. I have wracked my brains and all it achieved was to made the
> > phrase "finite automata" and the name "Henry Spencer" glow faintly on the
> > cusp of my consciousness, but I'm no closer to a solution. I can't even
> > think of a way to pose the question to Google.
> > 
> > I don't care what the pattern/s is/are, I just want to know for sure if one
> > (or more) exists. I'm not certain there is a solution, but I sure can't wait
> > forever to crawl through all possible strings to find out. I don't want some
> > kludge like limiting my string size (then trawling) or inventing my own
> > quasi-regex pattern matching system.
> 
> Regular expressions can be converted to finite state automata.  So
> what you want is an algorithm that can determine if the language
> accepted by two finite state automata intersect.
> 
> This page looks like it might be promising:
> http://odur.let.rug.nl/~vannoord/Fsa/

> It appears to have stuff both for converting regular expressions to
> finite state automaton, and for finding the intersection of finite
> state automaton.

Definitely worth looking at that - this looks like a pretty deep
problem to me, not one that would be obvious quickly.  If I hadn't
seen that page purporting to have an implementation of intersection I
wouldn't have been surprised if the problem turned out to be
NP-complete.

-- 
David Gibson			| For every complex problem there is a
david AT gibson.dropbear.id.au	| solution which is simple, neat and
				| wrong.
http://www.ozlabs.org/people/dgibson