A method for distributing sets of regular expressions to a fixed number of state machine engines includes combining, with a processing device, a plurality of regular expressions into a single compound regular expression, creating a single nondeterministic finite automaton (NFA) including a plurality of NFA states based on the compound regular expression, performing an interference analysis for each pair of NFA states to identify all pairs of NFA states that would potentially interfere in an equivalent deterministic finite automaton (DFA), creating an interference graph representing the regular expressions associated with potentially interfering NFA states based on the results of the interference analysis, and performing a graph coloring algorithm on the interference graph to assign a different color to each represented regular expression in the graph.