1. An apparatus for machine-translating a first language into a second language, comprising: an example storing unit that stores therein a first-language example in association with a second-language example that is a translation of the first-language example; a receiving unit that receives a first-language speech; a first recognizing unit that recognizes the first-language speech as a first-language character string, and outputs a first recognition result; a second recognizing unit that recognizes the first-language speech as a most probable first-language example from among first-language examples stored in the example storing unit, and outputs a second recognition result; a calculating unit that calculates a similarity between the first recognition result and the second recognition result; and a retrieving unit that retrieves, when calculated similarity exceeds a predetermined threshold, a second-language example corresponding to the second recognition result from the example storing unit.