I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that?
Also, can a Finite State Automaton have more than one starting state?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
FSAs come in several varieties. The most common ones are deterministic (DFA), nondeterministic (NFA), and nondeterministic with $\epsilon$-moves (also called NFAs; sometimes $\epsilon$-NFAs).
The definitions of all three are not completely standard – there are several variants in the literature (for example, some allow the transition function of a DFA to be partial). However, in most standard definitions, all FSAs have a single initial state; though it is perfectly possible to define NFAs and $\epsilon$-NFAs having several initial states.
The reason you have to add a new initial state when reversing an NFA is exactly the requirement that there be a unique initial state. If we remove this requirement, then there is no need to add a new initial state.
answered Sep 6 '18 at 2:45
