1
$\begingroup$

Can a finite automata not have a start state?

I think it is possible for a finite automata to not have a start state. However, I'm not sure if I'm correct.

$\endgroup$
1
  • 1
    $\begingroup$ What does the definition say? Overall, it's not important. You can simply say that automaton without starting state accepts an empty language. $\endgroup$
    – user114966
    Mar 28 at 19:16
3
$\begingroup$

It depends on the definition. Some definitions of a deterministic finite automaton (DFA) are a quadruplet $(Q, \delta, q_0, F)$ where $Q$ is the set of states and $q_0 \in Q$ is the initial state. Therefore, it must be defined.

However, the definition of non-deterministic finite automaton (NFA) is sometimes seen as a quadruplet $(Q, \Delta, I, F)$ where $Q$ is the set of states and $I\subset Q$ is the set of initial states. Here, you can chose $I = \emptyset$ and get an automaton without initial state.

Since a DFA can be seen as a special case of a NFA, it is not necessary for an automaton to have an initial state. In both cases (DFA and NFA), the language recognized by an automaton without initial state is $\emptyset$.

$\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.