Convert nondeterministic finite automaton to deterministic finite automaton?

Answer 1

The only difference between a NDFSA (non-deterministic finite-state automation) and a DFSA (deterministic finite-state automation) is that a NDFSA can be in several states at once. Therefore, to convert a NDFSA to a DFSA, all that needs to be done is to replace all transitions from a state that puts the FSA into multiple other states with one transition that puts it into a *new* single state (that will represent the multiple states) and will take all transitions off those multiple states.

if we say a.x->b means that from state "a", on input "x", goes to state "b", and have the following NDFSA

a.x->b

a.x->c

b.y->a

c.y->b

c.z->c

..make it a DFSA by:

a.x->b

a.x->c

{ create new state with all ND transitions }

i=(b,c)

i.y->a (from b.y)

i.y->b (from c.y)

i.z->c (from c.z)

{ a.x is now deterministic }

a.x->i

{ continue through each state }

i.y->a

i.y->b

{ make deterministic }

j=(a,b)

j.x->i (from a.x)

j.y->a (from b.y)

{ remove all unreachable states }

a.x->i

i.y->j

i.z->c

j.x->i

j.y->a

c.z->c

Remember that epsilon transitions (transitions a->b (with no x) will cascade), e.g.,

a.x->b

b->c

c->d

{ because "b" reaches "c", and "d" }

i=(b,c,d)

a.x->i