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.