Regular expressions can be visualized using railroad or syntax diagrams. The construction does not depend on fancy artistic skills. Rather, a diagram can be systematically constructed through simple, local transformations due to Manna. We argue that the result can be seen as a nondeterministic finite automaton with ε-transitions. Despite its simplicity, the construction has a number of pleasing characteristics: the number of states and the number of edges is linear in the size of the regular expression; due to sharing of sub-automata and auto-merging of states the resulting automaton is often surprisingly small. The proof of correctness relies on the notion of a subfactor. In fact, Antimirov's sub-factors (partial derivatives) appear as target states of non-ε-transitions, suggesting a smooth path to nondeterministic finite automata without ε-transitions. Antimirov's subfactors, in turn, provide a fine-grained analysis of Brzozowski's factors (derivatives), suggesting a smooth path to deterministic finite automata. We believe that this makes a good story line for introducing regular expressions and automata.
展开▼
