[Solved]: What is the difference between following two finite automata?

Problem Detail: 

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:

But somewhere in solution it is given the following diagram:

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?

Asked By : Kaushal28

Answered By : Filip Haglund

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61159

3.2K people like this

 Download Related Notes/Documents