Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Comparative satisfiability of regexps.

by blokhead (Monsignor)
on Jan 19, 2005 at 22:56 UTC ( #423543=note: print w/ replies, xml ) Need Help??


in reply to Comparative satisfiability of regexps.

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.

  1. Convert both regular expressions to equivalent NFAs. This is probably the most annoying part as you need a regex parser. This can be done in linear time.
  2. Convert the NFAs to DFAs. This is the part that takes exponential time in the general case.
  3. Do a product construction on the two DFAs, setting the accept states appropriately so the result accepts the symmetric difference of the two languages. This is done in quadratic time.
  4. Check to see if the resultant DFA accepts the empty language. This is easily done in linear time with a DFS/BFS traversal. If so, then the two regular expressions you started with were equivalent. If not, you can report back any string which this DFA accepts as a counterexample to their equivalence (such a string would be in one language but not the other).
A review of the first few chapters of your favorite automata book might be helpful to fill in the gaps. I have the old classic Intro to Automata Theory, Languages & Computation by Hopcroft/Ullman. It goes through these constructions with an algorithmic feel, which you might appreciate.

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


Comment on Re: Comparative satisfiability of regexps.
Re^2: Comparative satisfiability of regexps.
by Meowse (Beadle) on Jan 20, 2005 at 10:29 UTC
    Thank you, my friend. That is precisely the level, type, and depth of answer I was looking for. There's lots in there that I'll need to research, but that's where the meat of the problem is--in the learning.

    My, but it's been a long time since I formally studied regular expressions and finite automata. I can remember, vaguely, remembering being good at them. But I can't even remember being good at them, and I'm certainly not good at them now.

    Ullman? I TA'd Introduction to Computer Science for Dr. Ullman, back in the day. Smart, smart man. And now I'm heading back to the well to tank myself up. Small world. :-)

    Thanks again for the help, blokhead. And if/when I actually get some working code out of this in the direction of your above-mentioned "regular language playground module", I'll be sure to post about it here.

    Gratefully yours,

    Mickey.

Re^2: Comparative satisfiability of regexps.
by exussum0 (Vicar) on Jan 20, 2005 at 21:39 UTC
    Just to append to your CS theory regexp, you can't use memory beyond storage for the original string and the regular expression itself. Backrefs require memory to store values and do manips on them.

    ----
    Give me strength for today.. I will not talk it away..
    Just for a moment.. It will burn through the clouds.. and shine down on me.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://423543]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2014-09-16 01:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (155 votes), past polls