AUTOMATON DETERMINIZATION METHOD, DEVICE, AND COMPUTER PROGRAM PRODUCT

摘要

In an embodiment, an automaton determinization method includes: state-generating, first-transition-generating, second-transition-generating, and first-deleting. The state-generating includes generating, assigned with a first symbol, a second state newly. The first-transition-generating 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. The second-transition-generating includes generating, regarding the first transitions, a fourth transition where a state previous to a third transition is substituted with the second state. The third transition is an outgoing transition from a next state of the first transition. The first-deleting includes deleting states that are next to the first transitions where 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 where the fourth transitions are generated.

主权项

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 andthat 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, anddeleting the first transitions in which the fourth transitions are generated.