0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.