Inverting a regular expression?

ruby-talk
1

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

2

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://bitwi.se/\!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

3

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

···

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.

4

Dan Doel, May 4:

> 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

···

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

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