Systems Analysis and Synthesis

Appendix A

Regular expressions and finite-state automata

Abstract

Regular Expressions and Finite-state Automata explores the relationship between state-based and grammar-based descriptions of system behaviour. Even though behaviour-based descriptions make no mention of states, they are no more abstract than state-based descriptions, since every regular expression directly corresponds to a non-deterministic automaton and vice versa. It is straightforward to convert a regular expression into a workable but inefficient NFA, whose structure is essentially the same as the structure of the expression. It shows how to obtain a more efficient implementation, by optimising the NFA to give a DFA. It illustrates that optimisation often causes a profound change ...