Patent Document ID: 9177252
Application ID: 13755201
Patent Flag: 1

Claim One:
1. A method of constructing a composite DFA (deterministic finite automaton) using subset construction, said method comprising: compiling at least one single-rule DFA; performing a first subset construction on said at least one single-rule DFA to generate a first composite DFA, retaining subset information for said first composite DFA; compiling at least one new rule into at least one corresponding additional single-rule DFA; performing a second subset construction to generate a second composite DFA, wherein said first composite DFA acts as a first NFA (non-deterministic finite automaton) input for said second subset construction and said at least one corresponding additional single-rule DFA acts as at least one additional NFA input for said second subset construction, retaining subset information for said second composite DFA; searching said subset information for subsets containing single-rule DFA states corresponding to a rule to be deleted; deleting all single-rule DFA state references found during the search from said subset information; and deleting any composite DFA state whose subset becomes empty after said step of deleting all single-rule DFA state references.