Information processing apparatus, information processing method, and computer program product for reducing states in a deterministic finite state automaton

An information processing method comprising:

• classifying first states included in a deterministic finite automaton into state sets, the state sets having same input symbols associated with outgoing transitions and same finality indicating whether a state in the first states is a final state;
• calculating, for each of the state sets, an intersection set between each of the state sets and a set of transition destination states which is obtained by translating each of states included in the state set;
• repeating a calculation of the intersection set, until the number of states included in the intersection set becomes equal to one, while regarding the set of the transition destination states for each of the input symbol included in the intersection set as new state sets;
• and
• merging plural indistinguishable states into one state by tracing a route in a reverse direction to a transition direction, when the number of states has become equal to one.

A computer program product having a computer readable medium including programmed instructions for reduction in the number of states in a deterministic finite state automaton, wherein the instructions, when executed by a computer, cause the computer to perform:

• classifying first states included in a deterministic final automaton into state sets, the state sets having same input symbols associated with outgoing transitions and same finality indicating whether a state in the first states is a final state,
• calculating, for each of the state sets, an intersection set between each of the state sets and a set of transition destination states which is obtained by translating each of states included in the state sets;
• repeating a calculation of the intersection set, until the number of states included in the intersection set becomes equal to one, while regarding the set of the transition destination states for each of the input symbol included in the intersection set as new state sets;
• and
• merging plural indistinguishable states into one state by tracing a route in a reverse direction to a transition direction, when the number of states has become equal to one.