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?
Can it be decided whether there exists a string accepted by a given NFA at least k ways?
turing machines;finite automata;undecidability