5
$\begingroup$

I'm solving problem of drawing the finite automata of (1+0)*(10). Which is any string ends with 10. I've drawn the following diagram for this one:

My DFA diagram

But somewhere in solution it is given the following diagram:

Diagram from the solution

I can't understand what is the difference between these two? Is my solution is correct? If it is not than what changes in my solution will take me to this given solution?

$\endgroup$
  • 5
    $\begingroup$ Yours is non-deterministic. $\endgroup$ – pdexter Aug 1 '16 at 16:32
  • $\begingroup$ @pdexter what is the exact difference? Is there any general method to convert from non-deterministic to deterministic? Or I've to draw it directly by using some other method? If it is so, can you suggest the best way for this? Because I can't find the exact method in my book or on INTERNET. Thank you in advance :) $\endgroup$ – Kaushal28 Aug 1 '16 at 16:55
  • 3
    $\begingroup$ The wiki page for ndfa has information about it's equivalence to dfa. That's probably the best place to start. $\endgroup$ – pdexter Aug 1 '16 at 16:59
  • 1
    $\begingroup$ You should have covered nondeterminism in your automata theory class. Yes, there is a standard way of converting nondeterministic automata to deterministic ones, though it tends to lead to very large automata ($3$ states becomes $2^3=8$, which you then have to tidy up). $\endgroup$ – David Richerby Aug 1 '16 at 19:26
5
$\begingroup$

As many have pointed out in the comments, your automata is non-deterministic. There are two paths you could take from q0 when you read a 1. When running a non-deterministic automata, you need to keep track of all possible paths and see if any of them end up in an accepting state. If you don't keep track of all different possible states you could be in, your solution might never accept any string, if it choses the looping 1 all the time, never leaving q0.

Converting a non-deterministic finite automata (NFA) to a deterministic finite automata (DFA) can be done using a simple algorithm. It's quite slow, but for small examples, it's no problem doing it by hand. There are good videos explaining how to do this in slightly different ways.

The main idea is that you build a table of all possible states you could be in. For your NFA, I'll label the nodes q0, q1 and q2 from left to right, starting at q0.

  • At q0 we can reach q0 or q1 when reading a 1.
  • At q0 we can reach q0 when reading a 0.

That's the first step. Now we have multiple states at the same time. We already did q0 so we have the (q0 or q1) state left.

  • When reading a 1 from (q0 or q1) we can end up in (q0 or q1). q0 can reach (q0 or q1), and q1 cannot reach anywhere.
  • When reading a 0 from (q0 or q1) we can end up in (q0 or q2). q0 can loop back to itself, and q1 can reach q2.

And lastly, the (q0 or q2) state.

  • When reading a 0 from (q0 or q2) we can end up in q0. q2 doesn't have any outgoing edges, and q0 can only reach itself.
  • When reading a 1 from (q0 or q2) we can end up in (q0 or q1). q2 doesn't have any outgoing edges, and q0 can reach (q0 or q2).

Those are all our possible state transitions in the NFA.

Our list of states used in the transitions above are:

  • q0
  • (q0 or q1)
  • (q0 or q2)

The edges are:

  • q0 + 0 -> q0
  • q0 + 1 -> (q0 or q1)
  • (q0 or q1) + 0 -> (q0 or q2)
  • (q0 or q1) + 1 -> (q0 or q1)
  • (q0 or q2) + 0 -> q0
  • (q0 or q2) + 1 -> (q0 or q1)

You can see that this is the bottom graph in your question, with the states renamed.

It's worth noting that in real life regex engines, NFA's are used because this conversion is very expensive for large automata. It's cheaper and safer to keep track of all states instead of doing the conversion. One notable example is the RE2 library. Most other implementations use backtracking, which is O(2^n) for an n-length string. RE2 is exponential in the expression length, but linear in input. Developers write the expressions, attackers write the input.

$\endgroup$
  • $\begingroup$ Thank you very much. But I want to ask you that can I draw DFA directly from the given regular expression? or every time I've to first draw NFA and than I've to convert it to DFA? I've seen the video that you've mentioned in the answer. $\endgroup$ – Kaushal28 Aug 2 '16 at 12:05
  • $\begingroup$ It's easier to convert a regular expression to an NFA and then the NFA to a DFA. $\endgroup$ – Filip Haglund Aug 2 '16 at 12:14
  • $\begingroup$ but i think it is lengthy process when the regular exp. is complex. $\endgroup$ – Kaushal28 Aug 2 '16 at 12:16
2
$\begingroup$

The difference is that yours is a Nondeterministic finite automaton, given a symbol $1$ of the string you can either stay in state $q_0$ or go to state $q_1$, but how do you decide which one? (remember that both DFA's and NFA's have no memory!).

That's when you have a non determinism, you keep consuming symbols of the string, at some point you make a guess "Well I'm in the last two symbols of my given string, lemme see if I can reach the end State", if it ends with $10$, then you'll go to $q_1 \rightarrow q_2$, otherwise you'll remain in $q_0$.

The solution given in your book is an equivalent DFA, as it was already told in the comments you can take your NFA and convert it to an equivalent DFA.

$\endgroup$
0
$\begingroup$

Both are right answers. The finite automata you have drawn is actually NFA (Non-deterministic Finite Automata) And in the Second diagram (the answer in solution) is DFA (Deterministic Finite Automata)

As the name suggest, Non-deterministic, NFA may have more than one transition from a state for a single input symbol. That is, in your first diagram On seeing input symbol 1 at q0 state, the machine can remain in q0 itself or it can go to next state. But in DFA, for every state you need to define EXACTLY ONE transition for each input set.

Now, an answer to your doubt is the second diagram is more appropriate. Why..??!! Because every language has many finite automata. That is for language (1+0)* 10 , I can draw many NFAs and Many DFAs.

But every regular language has unique minimal DFA and that minimal DFA should be your answer for such type of question.

For minimization of DFA, you may refer following links. (1) Link-1 (2) Link-2

Note that, you can first draw NFA and convert it to equivalent DFA. But it is not the only way. By practice, you can directly draw the DFA for the given regular language.

$\endgroup$
  • 1
    $\begingroup$ "that minimal DFA should be your answer for such type of question." -- citation needed. $\endgroup$ – Raphael Aug 3 '16 at 9:05
  • 1
    $\begingroup$ What "should" be your answer is a matter of opinion. There's no basis for claiming that the minimal DFA "should" be your answer or is a better answer. "Citation needed" is a sort of Internet-shorthand for saying "what's your evidence for that claim?". The question is not evidence that supports your claim. $\endgroup$ – D.W. Aug 3 '16 at 20:20
  • $\begingroup$ Citation -- For uniqueness and all the leading reference books are following this convention. @D.W. $\endgroup$ – Krunal Aug 4 '16 at 5:53

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.