Visualizing regular expressions with reAnimator

reAnimator — a very cool tool for visualizing regular expressions. Given an RE, renders the corresponding NFA and DFA and animates acceptance (or not) of an input string. Try out the “a|ab|abc|abcd” example with input “a” for a neato example. A flash app, written using python.

3 Responses to “Visualizing regular expressions with reAnimator”

  1. January 16th, 2008 | 1:52 pm

    That’s very cool. Would certainly be useful for students when looking at regular expressions and finite automata in the first and second year CS.

    One thing that niggled at me though, with the DFA it generates, it doesn’t seem to have all the technically necessary states/transitions. While it’s still clear what is going on, using for example the regex “a*b|b*a”, and then input “aaab”, the final state it is in at that point on the DFA has no transitions leaving it, whereas from what I remember there should be transitions for every possible symbol to some state for DFAs, since at each step, a transition needs to be uniquely determined, being pedantic at least. I seem to remember Dr Rogenbach catching Dr Beckmann and the rest of our class out by showing what looked like a DFA but without this property and asking which it was. So in that case, I’d have thought there should be two transitions a,b that lead to a non-final state that then has transitions a,b to itself or something (so if you got to that final state and then added anything you got stuck in a non-final state so would never match after that?

    Looks cool anyway :)

  2. January 16th, 2008 | 2:31 pm

    You mean a “non accepting error state”? An “exception handler”? ;-) I guess that’s usually omitted for brevity; but yeah, I take your point.

    I’ve pointed this tool out to my colleagues, and in particular Dr Roggenbach and Mr Whyley (for CS-132 and CS-218 respectively). And I’ll certainly point my own tutees at it…

  3. Anon
    February 10th, 2008 | 7:24 pm

    So fancy. Back in the day vim and incremental search used to be enough…