Patent Document ID: 8943063
Application ID: 13648432

Base Claim:
1. A computer-implemented method for generating a tunable finite automaton (“TFA”) from 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 TFA having, at most, a number b of concurrent active states, the computer-implemented method comprising: a) receiving, as input by a computer system including a least one processor, a deterministic finite automaton (“DFA”) representation of the NFA; b) regrouping, with the computer system, the NFA active state combination associated with each state of the DFA into up to b subsets, with the objective of minimizing the number of total distinct subsets; c) generating, with the computer system, one TFA state for each of the distinct subsets; d) for each of the DFA states, storing, with the computer system, pointers to the up to b TFA states in a table entry associated with the NFA active state combination of the DFA state; e) associating, with the computer system, each of the TFA states with appropriate transition representations using the transition functions of the NFA states corresponding to the TFA state; f) storing, with the computer system, each of the TFA states; and g) storing, with the computer system, for each of the TFA states, each of the appropriate transition representations in association with the TFA state and a corresponding input symbol, wherein the number b is a specified parameter and is at least 2.

---

Claim 3:
3. The computer-implemented method of claim 1 , further comprising: receiving, as input, with the computer system, a set of regular expressions; generating, with the computer system, an NFA from the received set of regular expressions; and generating, with the computer system, the received DFA representation of the NFA using a subset construction scheme, such that states of the generated DFA provide all valid active state combinations of the NFA.