[clug] OT meta-regex question

[David Price]

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.

Good luck,
David