Patent ID: 8275730
Filing Date: 2012-09-25
Classification: G06N

Abstract:
1. An information processing apparatus comprising: a state classifying unit that classifies 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; a calculating unit that calculate, 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; a repeating unit that repeats 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 a state merging unit that merges 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.