Problem Detail: Is there a rule that either every DFA contains or not, a loop(cycle in graph terminology)? I do not seem to be able to generalize this idea in either direction. Also if either of these is true, can we assume through DFA – NFA equivalence that the same is true for NFAs?
Asked By : v k
Answered By : Yuval Filmus
Every finite directed graph in which every vertex has outdegree at least 1 has a cycle. This is a nice exercise. Thus, even if you look only at edges labeled by a particular symbol, you will find a cycle in every DFA.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/64397
