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
0 comments:
Post a Comment
Let us know your responses and feedback