4
$\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$
  • 3
    $\begingroup$ What if your DFA only accepts the string $010000000$, does it really needs a loop? $\endgroup$ – Aristu Oct 9 '16 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 Oct 9 '16 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 Oct 9 '16 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 Oct 9 '16 at 13:10
  • 1
    $\begingroup$ Yes, every DFA either contains a loop or not... $\endgroup$ – user253751 Oct 9 '16 at 23:29
11
$\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$
  • $\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 Oct 9 '16 at 13:23
  • 1
    $\begingroup$ There's none, since the outdegree of the accept state is 0. $\endgroup$ – Aristu Oct 9 '16 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 Oct 9 '16 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$ – Yuval Filmus Oct 9 '16 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 Oct 9 '16 at 13:51
4
$\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, privacy policy and cookie policy

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