Regular Expression Matching Using Associative Memory
This paper describes a method for the implementation of regular expression matching based on the use of a form of associative (or content addressable) memory. The regular expression matching is performed by converting the regular expression into a Deterministic Finite Automata, but then using associative memory to hold the state transition information. Rather than try to simplify the resulting automata, this approach starts from the point of view of each next state in the automata being arrived at from some particular area of state-input space. The authors implement their automata by defining a number of orthogonal regions of state-input space, each of which is compared against their current state and input data.