Число слов заданной длины в автоматном языке.

[max(Im)]

Доброго времени суток.
Задался таким вопросом - пусть есть конечный автомат-акцептор, который имеет одно начальное и одно заключительное состояние. Как оценить число слов заданной длины $n$ в его accepted language?

В поисках ответа нашел статью Хомского, Миллера про языки с конечным числом состояний. Там фактически рассматриваются автоматы с выделенным состоянием, которое является и конечным и начальным сразу. Оценка получается асимптотически $const\cdot r^n$ где $r$ - главный корень матрицы путей длины 1 автомата. Зависимость от алфавита лежит в const... Я прав, что оценка сохранится и для случая, когда инициальное состояние не финальное? Где можно про это прочитать? Я это вроде доказал, но сомневаюсь.

[Xaositect]

Зависит от того, в какой сильно связной компоненте лежит принимающее состояние. Асимптотика всегда будет экспоненциальной либо $O(1)$. Доказывается с помощью составления рекуррентного соотношения для чисел слов длины $n$, переводящих начальную вершину в какую-то и технической возни с теоремой Фробениуса-Перрона.