Patent Document ID: 8938454
Application ID: 13648438
Patent Flag: 1

Claim One:
1. For use in a system including a non-transitory computer-readable storage medium storing a data structure for emulating, with, at most, a number b of concurrent active states, a nondeterministic finite automaton (NFA) having a finite set of states, a finite set of input symbols and a transition function covering each state and input symbol, the data structure including (1) a plurality of tunable finite automaton (TFA) states, up to b TFA states representing any NFA active state combination, each of the plurality of states having at least one associated state label covering the finite set of input symbols, and (2) a table including a plurality of entries, each of the plurality of entries (i) including up to b pointers to up to b TFA states, the union of the up to b TFA states corresponding to one of the NFA active state combination, and (ii) being indexed by an NFA active state combination corresponding to a state of a deterministic finite automaton representation of the NFA, a computer-implemented method for determining whether an arbitrary sequence of input symbols matches a set of regular expressions represented by the NFA, the computer-implemented method comprising: a) defining, with a computer system including at least one processor, each of up to b of the plurality of TFA states as an initial state; b) receiving, with the computer system, a next symbol of the arbitrary sequence of input symbols; c) using the next symbol to determine, with the computer system, a state label associated with each of the up to b initial TFA states; d) using a union of the up to b state labels to determine, with the computer system, one of the plurality of entries of the table; e) deactivating, with the computer system, each of the up to b initial TFA states; f) activating, with the computer system, a next set of up to b TFA states using pointers stored in the entry; g) determining, with the computer system, if the next set of up to b active TFA states includes at least one match TFA state; h) if it was determined that the next set of up to b active TFA states include at least one match TFA state, then indicating, with the computer system, a match corresponding the at least one match TFA state; i) if there are no unprocessed symbols of the arbitrary sequence of input symbols, ending the method, otherwise, if there are any unprocessed symbols, 1) receiving, with the computer system, a next symbol of the arbitrary sequence of input symbols, 2) using the next symbol to determine, with the computer system, a state label associated with each of the active TFA states, 3) using a union of the up to b state labels to determine, with the computer system, a next one of the plurality of entries of the table, 4) deactiving, with the computer system, the active TFA states, 5) activating, with the computer system, a next set of up to b TFA states using pointers stored in the entry; 6) determining, with the computer system, if the next set of up to b active TFA states include at least one match TFA state, 7) if it was determined that the next set of up to b active TFA states include at least one match TFA state, then indicating, with the computer system, a match corresponding the at least one match TFA state, and 8) if there are no unprocessed symbols of the arbitrary sequence of input symbols, ending the method, otherwise, if there are any unprocessed symbols, repeating acts (i)(1) through (i)(8) while there are any unprocessed symbols of the arbitrary sequence of input symbols, wherein the number b is a specified parameter and is at least 2.