World's most popular travel blog for travel bloggers.

# [Solved]: Non-Deterministic FSA to Deterministic FSA, Two initial states

, ,
Problem Detail:

My method of conversion is by creating a reachable set tree and each set within the tree would represent the new states.

I have never dealt with FSAs that has 2 or more initial states. How do i create my reachable set tree with two or more states?

#### Answered By : Yuval Filmus

The powerset construction converts an NFA to a DFA. You then "optimize" the result by removing states which cannot be reachable from the start state. When the NFA has multiple starting states, you do exactly the same thing. The starting state of the new DFA is the state corresponding to the set of starting states in the NFA (compare that to the usual case, in which the starting state of the DFA is the signleton consisting of the starting state of the NFA).

Given a DFA, you can compute the set of reachable states iteratively: the starting state is reachable; any state which it points to is reachable; any state which these point to is reachable; and so on. (Technically, this is known as BFS. There are also other algorithms, such as DFS.)