Space-Time Tradeoff in Regular Expression Matching With Semi-Deterministic Finite Automata

Date Added: Mar 2011
Format: PDF

Regular Expression Matching (REM) with Non-deterministic Finite Automata (NFA) can be computationally expensive when a large number of patterns are matched concurrently. On the other hand, converting the NFA to a Deterministic Finite Automaton (DFA) can cause state explosion, where the number of states and transitions in the DFA are exponentially larger than in the NFA. In this paper, the authors seek to answer the following question: to match an arbitrary set of regular expressions, is there a finite automaton that lies between the NFA and DFA in terms of computation and memory complexities? They introduce the Semi-deterministic Finite Automata (SFA) and the state convolvement test to construct an SFA from a given NFA.