HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Does every DFA contain a loop?

Submitted by: @import:stackexchange-cs··
0
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?

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.