No such thing as a small change | |
PerlMonks |
Re: Comparative satisfiability of regexps.by blokhead (Monsignor) |
on Jan 19, 2005 at 22:56 UTC ( [id://423543]=note: print w/replies, xml ) | Need Help?? |
As long as you mean regular expressions in the CS-theory sense (no backrefs, etc), yes it's perfectly computable, although it takes exponential time (and space) in the general case. No, this is not as general as the undecidable question "are these two algorithms equivalent" that others have mentioned in this thread. The underlying critters we are dealing with are regular languages (not recursive languages), and all decision properties of regular languages (that I can think of, at least) are decidable.
Here's how a theory person would check if two regexes were equivalent. In fact, this is a very good question for a first exam in a computational models/formal languages class.
Of course, this begs the question, is there a regular language playground module, where I can take a regular language, perform all the closure property constructions, decision problems, and conversion between NFA/DFA/regex representations? And if not, why not? ;) Update: Fixed ISBN link (for some reason, the ISBN on the back of my edition wasn't recognized. blokhead
In Section
Seekers of Perl Wisdom
|
|