1. A computer-implemented method for performing morphological analysis of natural language sentences, comprising: retrieving words of a natural language sentence from a word dictionary stored within a word dictionary storage device; retrieving concatenation rules from a grammar dictionary, stored within a grammar dictionary storage device, for concatenation of said words, based on a part of speech of each retrieved word; creating a computer automaton corresponding to the natural language sentence based on the retrieved words and concatenation rules; and generating, responsive to entry of an input word into the computer automaton, states necessary for transition according to the concatenation rules corresponding to an input word without generating any state that is transited by pursuing a null transition succeeding the generated states.