A constructing method of a finite state machine with failure transitions FFM is disclosed. The machine FFM is constructed from a nondeterministic finite-state machine and a string of external inputs. States in the machine FFM is formed of a state set q included in the nondeterministic finite-state machine and a set p defined as a subset of the state set q, and the number of states is finite. Also, an external input c takes the machine FFM from a current state s to a next state g(s,c) and an output µ(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and an external input c takes the machine FFM from the current state s to a state g(f(f···f(s)···)) determined by repeatedly calculating a value f(s) of a failure function f until a value g(f(f···f(s)···)) defined is found out in cases where the value g(s,c) of the success function g is not defined. Because all of transitions from the current state s for all external inputs c are not defined by the success function g, a storage capacity for storing the machine FFM is considerably reduced.