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?

on 2006-03-11 17:50

on 2006-03-12 11:01

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

on 2006-03-12 11:20

On 12 Mar 2006, at 09:58, Dan Kohn 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(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.

on 2006-03-12 13:16

Benjohn Barnes <benjohn@fysh.org> wrote: > On 12 Mar 2006, at 09:58, Dan Kohn 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

on 2006-03-12 22:25

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