Сложность проблемы слов с наименьшим количеством различных букв, принимаемых конечным автоматом

Учитывая конечный (детерминированный или недетерминированный, я не думаю, что это имеет большое значение) автомат A и порог n , принимает ли A слово, содержащее не более n различных букв?

(Под k разными буквами я подразумеваю, что aabaa имеет две разные буквы, a и b .)

Я показал, что эта задача является NP-полной, но мое сокращение приводит к автоматам, в которых одна и та же буква появляется на многих переходах.

Меня скорее интересуют случаи, когда каждая буква появляется не более k раз в A, где k - фиксированный параметр. Проблема все еще NP-полная?

Для k = 1 проблема - просто кратчайший путь, как и для P. Для k = 2 я не смог ни показать членство в P, ни найти доказательство NP-твердости.

Любая идея, по крайней мере для к = 2?

$k=3$$3$$2$ предложениях.

$k$$st$$n$ цветов?

$s$$n$$n$$2n$$n$