A composite DFA for multiple regular expressions or other rules may be generated in a two-step process—first compiling single rule DFAs, then performing subset construction on those DFAs to generate the composite DFA, with subset information retained. A new batch of one or more rules may be added by another subset construction from the old composite DFA and new single rule DFAs, with subset information for the new composite DFA compressed into sets of states from old and new single rule DFAs. A batch of one or more rules is deleted by deleting references to single rule DFA states from composite DFA subsets, deleting composite DFA states with empty subsets and merging composite DFA states with identical subsets. Rules are changed by deleting the old versions and then adding the new versions.