Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Comment on

( #3333=superdoc: 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.

  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.


In reply to Re: Comparative satisfiability of regexps. by blokhead
in thread Comparative satisfiability of regexps. by Meowse

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others scrutinizing the Monastery: (7)
    As of 2018-03-24 23:49 GMT
    Find Nodes?
      Voting Booth?
      When I think of a mole I think of:

      Results (299 votes). Check out past polls.