Может быть попробовать разбирать предложение по частям? А затем отсеивать невозможные варианты пстановки сущствительного, а уже из оставшихся пытаться выковыривать существительные (методом исключения к примеру). И может заюзать это http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_% D1%81_%D0%BF%D0%BE%D0%B4%D0%BA%D1%80%D0%B5%D0%BF%D 0%BB%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC
------------------------------------------------------------------
Вечно меня маразм навещает на унитазе: а что если попробовать взять всевозможные окончания существительных и от них генерировать слова, а затем уже вести обучение системы.