Automaton determinization method, device, and computer program product that involves a plurality of states and deleting states that are next states to first transitions

1. An automaton determinization method comprising:

state-generating that includes

generating a second state newly, 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;

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 next states 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.

2. The method according to claim 1 , further comprising:

first-associating that includes associating the third transitions with the fourth transitions;

second-associating that includes associating, when the first transitions are associated with other transitions at the time of generating the second transition at the first-transition-generating, the generated second transition with the other transitions;

determining, when two states included in the finite state automaton satisfy a predetermined criterion regarding transitions that are associated with outgoing transitions from the two states, that the two states are equivalent; and

connection-changing that includes changing connection of a next state of an incoming transition that is incoming to one of the two states determined to be equivalent to the other of the two states.

3. The method according to claim 2 , wherein

the criterion points to a criterion that all transitions associated with an outgoing transition from one of the two states match with all transitions associated with an outgoing transition from the other of the two states.

4. The method according to claim 1 , further comprising:

third-associating that associates a next state of the first state to the second state;

fourth-associating that includes associating, when next states of the first transitions are associated with other states at the time of generating the second state at the state-generating, the generated second state with the other states;

determining, when two states included in the finite state automaton satisfy a predetermined criterion regarding states that are associated with the two states, that the two states are equivalent; and

connection-changing that includes changing connection of a next state of an incoming transition that is incoming to one of the two states determined to be equivalent to the other of the two states.

5. The method according to claim 4 , wherein

the criterion points to a criterion that all states associated with one of the two states match with all states associated with the other of the two states.

6. The method according to claim 1 , wherein

the finite state automaton is a weighted finite state automaton, and

the automaton determinization method further comprising

weight-calculating that includes calculating a weight of the second transition that represents most appropriate weight calculated from weights of the first transitions by performing predetermined operations.

7. The method according to claim 6 , further comprising:

fifth-associating that includes associating the third transitions with the fourth transitions and assigning weights of the fourth transitions to associations;

sixth-associating that includes associating, when the first transitions are associated with other transitions at the time of generating the second transition at the first-transition-generating, the generated second transition with the other transitions;

determining, when two states included in the weighted finite state automaton satisfy a predetermined criterion regarding transitions that are associated with outgoing transitions from the two states, that the two states are equivalent; and

connection-changing that includes changing connection of a next state of an incoming transition that is incoming to one of the two states determined to be equivalent to the other of the two states.

8. The method according to claim 7 , wherein

the criterion points to a criterion that all transitions and all associating weights associated with an outgoing transition from one of the two states match with all transitions associated and all associating weights with an outgoing transition from the other of the two states.

9. The method according to claim 1 , wherein

the finite state automaton is a finite state transducer, and

the automaton determinization method further comprises

symbol-sequence-calculating that includes calculating an output symbol sequence of the second transition that points to a symbol sequence of the longest common prefix of output symbol sequences of the first transitions.

10. The method according to claim 9 , further comprising:

seventh-associating that includes

associating the third transitions with the fourth transitions and

assigning output symbols of the fourth transitions to associations;

eighth-associating that includes associating, when the first transitions are associated with other transitions at the time of generating the second transition at the first-transition-generating, the generated second transition with the other transitions;

determining, when two states included in the finite state transducer satisfy a predetermined criterion regarding transitions that are associated with outgoing transitions from the two states, that the two states are equivalent; and

connection-changing that includes changing connection of a next state of an incoming transition that is incoming to one of the two states determined to be equivalent to the other of the two states.

11. The method according to claim 10 , wherein

the criterion points to a criterion that all transitions and all associating output symbol sequences associated with an outgoing transition from one of the two states match with all transitions and all associating output symbol sequences associated with an outgoing transition from the other of the two states.

12. The method according to claim 1 , further comprising

second-deleting that includes deleting, at a predetermined frequency, states and transitions that are not reachable from an initial state.

13. The method according to claim 12 , wherein, every time one of the state-generating, the first-transition-generating, the second-transition-generating, and the first-deleting is completed,

the second-deleting includes deleting states and transitions that are not reachable from an initial state.

14. 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.

15. 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.