patternModerate
Does every DFA contain a loop?
Viewed 0 times
dfacontainloopeverydoes
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#64397, answer score: 12
Revisions (0)
No revisions yet.