Information processing device, information processing method and computer program product

摘要

According to an embodiment, an information processing device includes a first set generating unit that generates a first set of states reachable by following ε-transitions in a forward direction and a reverse direction among states included in a finite state automaton; a second set generating unit that generates a second set representing a set of states included in each of a plurality of first sets connected by one transition that is not an ε-transition and the first set that is not connected to another first set by one transition that is not an ε-transition; a combination generating unit that obtains, among combinations of ε-removal patterns to be respectively applied to the ε-transitions in the second set, a combination with which the number of transitions after removing ε-transitions is the smallest; and a removing unit that removes ε-transitions in the second set by the removal patterns included in the obtained combination.

主权项

1. An information processing device comprising:
a hardware processor configured to control the information processing device to perform operations comprising: generating a plurality of first sets, each of the first sets representing a set of states that are reachable by following ε-transitions in a forward direction and a reverse direction among states included in a finite state automaton; generating, when the first sets are connected with one another by one transition that is not an ε-transition, a set of states included in each of the first sets connected by one transition that is not an ε-transition, and generating one or more second sets, each of the second sets representing the generated set and a first set that is not connected to another first set by one transition that is not an ε-transition; generating, for each of the second sets, a combination of removal patterns to be respectively applied to ε-transitions between states included in the second set among a plurality of predetermined removal patterns for removing an ε-transition, and obtaining, among the generated combinations, a combination with which the number of transitions in the second set after removing ε-transitions is the smallest; and removing, for each of the second sets, ε-transitions in the second set by the removal patterns included in the corresponding obtained combination.