5
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ What if your DFA only accepts the string $010000000$, does it really needs a loop? $\endgroup$
    – Aristu
    Commented Oct 9, 2016 at 12:49
  • 2
    $\begingroup$ After thinking about examples like @melchizedek's, then ask yourself what if its language is infinite (has an infinite number of strings)? $\endgroup$
    – usul
    Commented Oct 9, 2016 at 13:03
  • 1
    $\begingroup$ What have you tried and where did you get stuck? Have you looked at examples, and what have you found? What is the "meaning" of loops for the accepted languages? $\endgroup$
    – Raphael
    Commented Oct 9, 2016 at 13:04
  • 1
    $\begingroup$ I have as an assignment to prove by contradiction that every DFA contains a loop. But intuitively I cannot support this. There are DFAs without loops. I just wanted to know if there is a strict rule for this issue. $\endgroup$
    – vkoukou
    Commented Oct 9, 2016 at 13:10
  • 1
    $\begingroup$ Yes, every DFA either contains a loop or not... $\endgroup$ Commented Oct 9, 2016 at 23:29

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ How can we find a cycle in every DFA? If for example we have a DFA with only 2 states and 1 transition. e.g. a DFA accepting only the string a, with a start state and and an accepting state. Where is the cycle in this DFA? $\endgroup$
    – vkoukou
    Commented Oct 9, 2016 at 13:23
  • 1
    $\begingroup$ There's none, since the outdegree of the accept state is 0. $\endgroup$
    – Aristu
    Commented Oct 9, 2016 at 13:24
  • $\begingroup$ So, in order to get this straight more informally. There are some DFAs that do not have a cycle and some that have. But how I am supposed to prove that every DFA contains a cycle if this is the case? Is the exercise wrong? I am not looking for a solution, I am trying to understand how this statement can be true. $\endgroup$
    – vkoukou
    Commented Oct 9, 2016 at 13:28
  • 7
    $\begingroup$ I guess it depends on your definition of DFA. According to my definition, every state has an outgoing transition for every symbol. $\endgroup$ Commented Oct 9, 2016 at 13:43
  • 1
    $\begingroup$ Yes maybe I did not account the strict definition of DFAs. Thank you for help and your explanation of these details! $\endgroup$
    – vkoukou
    Commented Oct 9, 2016 at 13:51
5
$\begingroup$

There are two ways of looking at a DFA.

Some folks insist that every state must have a transition for every symbol in the alphabet (the transition function is a total function). If you look at a DFA this way, then, yes, as according to the accepted answer there will always be a cycle. But this cycle might be self-loop to some "dead" or "error" state.

On the other hand, some say that if there is no transition for a given symbol from a given state, then if the machine is in that state and that symbol is encountered, then the string is rejected.

Alas, many books on the subject define the transition function as per first example, but then draw state diagrams as per the second example.

But when it comes to a sequence of states that could potentially lead to the acceptance of a string, some have cycles, some do not. If a DFA recognizes an infinite language, its graph must contain at least one cycle that is not a self-loop to a dead state (this is a corollary of the Pumping Lemma for Regular Languages). If the graph of a DFA does not contain such a cycle, then it cannot recognize an infinite language.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.