World's most popular travel blog for travel bloggers.

[Solved]: Does every DFA contain a loop?

, , No Comments
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

0 comments:

Post a Comment

Let us know your responses and feedback