reviz - Visualize NFA and DFA constructed from basic regexp

Finite automatons constructed from ((a|b|c)*|(d|e)+)f

Try It

Build it with make, and try to visualize a simple regular expression, such as ((a|b|c)*|(d|e)+)f:

./reviz '((a|b|c)*|(d|e)+)f'

You will get three .ps files in your current working directory:

nfa.ps

NFA constructed directly from the regular expression

dfa.ps

DFA converted from that NFA

dfa_opt.ps

Optimized DFA constructed by merging undistinguishable states

You can inspect these FAs with any PostScript viewer.

Attention: You must have graphviz installed on your system

Overview

redot takes a simple regular expression from commandline and generate DOT files named nfa.dot, dfa.dot and dfa_opt.dot in current working directory, which are the finite automatons constructed from that regular expression. These dot files can be converted to various image formats by graphviz; reviz is a simple wrapper which calls redot and converts generated dot files to PostScript format, so the results can be displayed immediately with various document viewer programs.

The “regular expression” this program accepts were only the most basic building blocks. You can only use one or many of alternative operator |, Kleene star *, positive closure + and optional mark ? in your regular expression, and the vocabulary is also restricted (you can only use alnums as input characters). However I think that is just enough to show the underlying principles of regexp pattern matching.