Can it be decided whether there exists a string accepted by a given NFA at least k ways?

Can I think this way:

We can convert a NFA to a RE using GFA.

We build a series of GFAs. At each step, one state (other than start or accept) is removed and replaced by transitions that have the same effect.

So, if we can convert k REs which have different forms but accept same language, then there must exists a string that the NFA accepts along k paths.

Does that sound right?

How to prove it properly?

The idea is to use a construction very similar to the power set construction. In the usual power set construction, each NFA state has two possibilities: unreachable and reachable. In our case, each NFA state has three possibilities: unreachable, uniquely reachable, and multiply reachable. It is straightforward to carry out the construction, and I will not spell it out here. A state in the DFA is accepting if either it contains a multiply reachable NFA accepting state, or it contains at least two uniquely reachable NFA accepting states. There is a word accepted by the NFA using more than one path if the language of the new DFA is not empty. In fact, the language accepted by the DFA consists of all words accepted by more than one path.

Using the same idea, we can compute the language of words accepted by the NFA using exactly, at most, or at least $k$ paths.

StackExchange Computer Science Q#18109, answer score: 6