Regular Expression Intersection

Ruby
1

Regular languages are closed under intersection (as well as difference,
complement, and of course union).

I find myself needing to know whether two regexps intersect. That is,
whether the intersection of the two regexps is not empty.

I could code it up using the algorithm which can be found just about
anywhere regular language theory is sold, e.g.
http://www.cs.may.ie/~jpower/Courses/parsing/node13.html

But I wonder if there’s a better way to do this using ruby regular
expression tricks, or at least a way that is already coded up for me?

2

You’ll generally get a better answer if you include an example in your
question. Also, that link didn’t work.

If you’re asking how to apply two regexps, you can use the scan method
to get the results in arrays, and then intersect them with &.

string =“hello world”; puts string.scan(/…/) & string.scan(/…l/)

3

On 12 Mar 2006, at 09:58, Dan K. wrote:

You’ll generally get a better answer if you include an example in your
question. Also, that link didn’t work.

If you’re asking how to apply two regexps, you can use the scan method
to get the results in arrays, and then intersect them with &.

string =“hello world”; puts string.scan(/…/) & string.scan(/…l/)

I think he’s trying to do this…

If you have a regular expression, R, then there is a (potentially
infinite) set S® of input strings that it will match.

Given two regular expressions, R1 and R2, you can find the strings
that match either regular expression:
S(R1) & S(R2)

He now wants to find a regular expression Ri such that:
S(Ri) = S(R1) & S(R2)

And he’s looking for an algorithm that will calculate Ri given R1 and
R2. I think :slight_smile:

Given, say:
R1 = /hell/
R2 = /ello/

then I think that Ri = /hello/

:slight_smile: It could, perhaps, be a ruby quiz.

4

Benjohn B. [email protected] wrote:

On 12 Mar 2006, at 09:58, Dan K. wrote:

You’ll generally get a better answer if you include an example in
your question. Also, that link didn’t work.

If you’re asking how to apply two regexps, you can use the scan
method to get the results in arrays, and then intersect them with &.

This does not help at all as Benjon explains. The question is not
whether
there are some strings in a set of strings that are matched by both RX
but
whether there is at least one string among all possible strings that
is
matched by both.

He now wants to find a regular expression Ri such that:
S(Ri) = S(R1) & S(R2)

No. He wants to know whether S(R1) & S(R2) is not empty. At least
that’s
what he stated. You might be able to solve the problem by finding Ri
but
that was not the original problem stated.

Kind regards

robert
5

Robert K. wrote:

whether there are some strings in a set of strings that are matched by
both RX but whether there is at least one string among all possible
strings that is matched by both.

…

No. He wants to know whether S(R1) & S(R2) is not empty. At least
that’s what he stated. You might be able to solve the problem by
finding Ri but that was not the original problem stated.

Yes, precisely.

I figured out how to do it manually for this application which uses a
simple regex syntax. Doing it for the Regexp class in general would be
quite another thing.

Having now done it, I think it would make a great quiz, with a little
head start (which I am willing to give). Are you listening James?

If anyone’s interested in the solution I came up with let me know.