1. Apparatus for performing morphological analysis of natural language sentences, comprising: a word candidate retrieving means for retrieving words of a natural language sentence from a word dictionary; a concatenation rule retrieving means for retrieving concatenation rules for concatenation of words from a grammar dictionary based on a part of speech of each word retrieved by said word candidate retrieving means; and a searching means for searching for an optimal solution of morphological analysis by creating an automaton corresponding to the natural language sentence based on the words retrieved by said word candidate retrieving means and the concatenation rules retrieved by said concatenation rule retrieving means; wherein said searching means generates, responsive to an input word entered into the automaton, states necessary for transition according to the concatenation rules corresponding to the input word without generating any state that can be transited by pursuing a null transition succeeding the generated states.