[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Regular Expression Intersection

Hans Fugal

3/11/2006 4:47:00 PM

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

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?
4 Answers

Dan Kohn

3/12/2006 9:57:00 AM

0

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

3/12/2006 10:19:00 AM

0


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.

Robert Klemme

3/12/2006 12:12:00 PM

0

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.

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

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

3/12/2006 9:21:00 PM

0

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

....

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