- Home
- Search
- Settings
- Top Contributors
- Help Center
Convert nondeterministic finite automaton to deterministic finite automaton?
Answer:
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 multipe 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
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
First answer by ID1499746604.
Last edit by ID1499746604.
Question popularity:
2
[recommend question].
How can you get the hidden item in twisted thicket?
In: Poptropica
Answer it!
What is a good name for a strawberry roan horse?
In: Care of Horses
Answer it!
What birds have single wing bars?
In: Birds
Answer it!
» more