Forum: Ruby Regular Expression Intersection

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Ec594ddcaeae2771ee9d0dd7f0d598ed?d=identicon&s=25 Hans Fugal (Guest)
on 2006-03-11 17:50
(Received via mailing list)
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?
5730f209b34b8474639e0c2020f54513?d=identicon&s=25 Dan Kohn (Guest)
on 2006-03-12 11:01
(Received via mailing list)
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/)
Ffcb418e17cac2873d611c2b8d8d891c?d=identicon&s=25 Benjohn Barnes (Guest)
on 2006-03-12 11:20
(Received via mailing list)
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.
5befe95e6648daec3dd5728cd36602d0?d=identicon&s=25 Robert Klemme (Guest)
on 2006-03-12 13:16
(Received via mailing list)
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
Ec594ddcaeae2771ee9d0dd7f0d598ed?d=identicon&s=25 Hans Fugal (Guest)
on 2006-03-12 22:25
(Received via mailing list)
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.
This topic is locked and can not be replied to.