Equivalent Regular Expressions

The following two Regular Expressions (RE) are equivalent:

b^*(ab)^*aa(a+b)^* = (a+b)^*aa(a+b)^*

Drawing the Non-Deterministic Finite Automata (NFA) makes it easier to ferret out the RE than drawing the “strictly” Deterministic Finite Automata (DFA).

Chad Salinas find an equivalent RE example.

This entry was posted on Wednesday, June 27th, 2007 at 8:12 pm and is filed under Discrete Structures. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Equivalent Regular Expressions”

  1. John Williams Says:
    June 27, 2007 at 10:13 pm

    Ferret out?? I’ve wondered about the origins of this idiom. Do ferrets search? Bloodhounds do. Do ferrets retrieve? Perhaps we could invent a new database model and call the UI Ferret?

Leave a Reply