Regular Expression Intersection

[Hans Fugal]

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?

 

[Dan Kohn]

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

 

[Benjohn Barnes]

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(R) 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

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

then I think that Ri = /hello/

It could, perhaps, be a ruby quiz.

 

[Robert Klemme]

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.

I think he's trying to do this...

If you have a regular expression, R, then there is a (potentially
infinite) set S(R) 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)

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

 

[Hans Fugal]

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

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.