Złożoność problemu słów z najmniejszą liczbą wyraźnych liter akceptowanych przez automat skończony

Biorąc pod uwagę skończony (deterministyczny lub niedeterministyczny, nie sądzę, że ma to duże znaczenie) automat A i próg n , czy A akceptuje słowo zawierające najwyżej n odrębnych liter?

(Przez k różnych liter rozumiem, że aabaa ma dwie różne litery, a i b .)

Pokazałem, że ten problem jest NP-zupełny, ale moja redukcja produkuje automaty, w których ten sam list pojawia się na wielu przejściach.

Raczej interesują mnie przypadki, w których każda litera pojawia się co najwyżej k razy w A, gdzie k jest stałym parametrem. Czy problem jest nadal NP-zupełny?

Dla k = 1 problem jest po prostu najkrótszą ścieżką, podobnie jak P. Dla k = 2 Nie byłem w stanie pokazać członkostwa w P ani znaleźć dowodu twardości NP.

Jakiś pomysł, przynajmniej dla k = 2?

$k=3$$3$$2$

$k$$st$$n$

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