Automaton determinization method, device, and computer program product

An automaton determinization device comprising:

• a state generating unit configured to, when there are two or more first transitions that leave from a first state included in a finite state automaton and that are assigned with a first symbol, newly generate a second state;
• a first transition generating unit configured to generate a second transition
• that leaves from the first state and enters to the second state and
• that is assigned with the first symbol;
• a second transition generating unit configured to generate, with respect to each of the first transitions, a fourth transition that in which a state previous to a third transition is substituted with the second state,
• the third transition being an outgoing transition from a next state of the first transition;
• and
• a first deleting unit configured to
• delete states which are next states to the first transitions for in which the fourth transitions are generated and that do not have incoming transitions other than the first transitions,
• delete outgoing transitions from the deleted states, and
• delete the first transitions in which the fourth transitions are generated.

A computer program product comprising a computer-readable medium including programmed instructions for automaton determinization, wherein the instructions, when executed by a computer, cause the computer to perform:

• state-generating that includes
• generating, when there are two or more first transitions that leave from a first state included in a finite state automaton and that are assigned with a first symbol, a second state newly;
• first-transition-generating that includes generating a second transition
• that leaves from the first state and enters to the second state and
• that is assigned with the first symbol;
• second-transition-generating that includes generating, with respect to each of the first transitions, a fourth transition in which a state previous to a third transition is substituted with the second state,
• the third transition being an outgoing transition from a next state of the first transition;
• and
• first-deleting that includes
• deleting states that are next states to the first transitions in which the fourth transitions are generated and that do not have incoming transitions other than the first transitions,
• deleting outgoing transitions from the deleted states, and
• deleting the first transitions in which the fourth transitions are generated.