According to an embodiment, a conversion device converts a first automaton into a second automaton, which both are weighted finite state automatons. The first automaton has a boundary of a path assigned with an input symbol, an appearance position of the boundary, and identifiers for identifying paths. The second automaton has path(s) except unnecessary path(s). The device includes a specifying unit and a search unit. The specifying unit is configured to specify, as a start position, a state of the head of a retrieved path in which a combined weight, which is obtained by adding an accumulated weight from an initial state to the state of the head of the retrieved path in the first automaton and a weight of the best path from the state of the head of the retrieved path to a final state, is best. The search unit is configured to search for a path in which a weight from the start position to a final state in the first automaton is best until reaching next boundary.