Automaton determinization method, device, and computer program product involving deleting states

摘要

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. A method for determinizing an automaton using a computer including a processor and storage, the method being performed under control of the processor and comprising:
loading a finite state automaton into the storage; 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 the finite state automaton and that are assigned with a first symbol; storing the second state in the storage; 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; storing the second transition in the storage; 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; storing the fourth transitions in the storage; first-deleting to reduce an amount of storage used by the determinizing, the first-deleting including
deleting from the storage 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 from the storage outgoing transitions from the deleted states, anddeleting from the storage the first transitions in which the fourth transitions are generated; and outputting the finite state automaton on which the first-deleting is performed as a determinized finite state automaton.