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


 

Forums >

comp.lang.ruby

Re: Inverting a regular expression?

Harry Ohlsen

5/4/2005 8:20:00 AM

> From: Dan Doel [mailto:dolio@case.edu]
>
> 1) Convert the regex to a DFA
> 2) Invert the accept states of the DFA, causing it to accept the
complement
> of the initial language
> 3) Convert the modified DFA into a regex

Good point! I assume steps 1 and 2 are left as exercises for the reader
:-).

> However, it should be noted that regular expressions aren't really
regular
> these days. For example, Ruby allows the following regex:
>
> /(a*)b(\1)/

> Which accepts the language { (a^n)b(a^n) }, which is context free, not
> regular (that is, it cannot be encoded as the language of a finite
> automaton---it requires something like a pushdown automaton (FA with a
> stack)---or the language of a true regular expression---it requires a
> context free grammar). So, if you want to invert an arbitrary
> Ruby/Perl/Python "regular expression," you've got a tougher time on
your
> hands.

Another good point. Yes, REs as used in computer languages have
certainly moved on.

Thanks for the insight.

H.


************************************************************************

If you have received this e-mail in error, please delete it and notify the sender as soon as possible. The contents of this e-mail may be confidential and the unauthorized use, copying, or dissemination of it and any attachments to it, is prohibited.

Internet communications are not secure and Hyperion does not, therefore, accept legal responsibility for the contents of this message nor for any damage caused by viruses. The views expressed here do not necessarily represent those of Hyperion.

For more information about Hyperion, please visit our Web site at www.hyperion.com
3 Answers

Nikolai Weibull

5/4/2005 10:06:00 AM

0

Harry Ohlsen, May 4:

> > From: Dan Doel [mailto:dolio@case.edu]

> > 1) Convert the regex to a DFA
> > 2) Invert the accept states of the DFA, causing it to accept the
> > complement of the initial language
> > 3) Convert the modified DFA into a regex

> Good point! I assume steps 1 and 2 are left as exercises for the reader
> :-).

Actually, it's not a very good point, as it isn't quite right. See my
response to this thread for the corrected method of conversion.

> > However, it should be noted that regular expressions aren't really
> > regular these days. For example, Ruby allows the following regex:

> > /(a*)b(\1)/

> > Which accepts the language { (a^n)b(a^n) }, which is context free,
> > not regular (that is, it cannot be encoded as the language of a
> > finite automaton---it requires something like a pushdown automaton
> > (FA with a stack)---or the language of a true regular
> > expression---it requires a context free grammar). So, if you want to
> > invert an arbitrary Ruby/Perl/Python "regular expression," you've
> > got a tougher time on your hands.

> Another good point. Yes, REs as used in computer languages have
> certainly moved on.

Well, some would say that it's evolution, while others would call it an
utter disregard of the rules. Again, backreferencing is an NP-complete
problem, which, as you know, has some dire implications,
nikolai

--
Nikolai Weibull: now available free of charge at http:/...!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

Dan Doel

5/4/2005 11:28:00 AM

0

On Wednesday May 4 2005 6:06 am, Nikolai Weibull wrote:
> Actually, it's not a very good point, as it isn't quite right. See my
> response to this thread for the corrected method of conversion.

What was wrong with my method? DFAs are required to be fully defined/complete
(at least, that's how I was taught), so there will never be a need to add a
sink state, as you're required to have one already (only an NFA can be
missing transitions).

And by "invert the accept states," I meant exactly what you said later: "make
any accept state non-accepting and any non-accepting state accepting." I
suppose I should have worded it more precisely.

My method was no different than yours.

-- Dan Doel

Nikolai Weibull

5/4/2005 11:48:00 AM

0

Dan Doel, May 4:

> On Wednesday May 4 2005 6:06 am, Nikolai Weibull wrote:

> > Actually, it's not a very good point, as it isn't quite right. See my
> > response to this thread for the corrected method of conversion.

> What was wrong with my method? DFAs are required to be fully defined/complete
> (at least, that's how I was taught), so there will never be a need to add a
> sink state, as you're required to have one already (only an NFA can be
> missing transitions).

I stated this in my initial response as well.

> And by "invert the accept states," I meant exactly what you said later: "make
> any accept state non-accepting and any non-accepting state accepting." I
> suppose I should have worded it more precisely.

Again, that's what I said in my initial response. I just wanted to
clarify a bit, as Harry for some reason didn't continue his discussion
on that sub-thread. I'm not trying to discredit you,
nikolai

--
Nikolai Weibull: now available free of charge at http:/...!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}