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

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 and
• that 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, and
• deleting 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.