HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Nondeterministic finite state machine without any initial state possible

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
withoutfiniteanypossiblestateinitialnondeterministicmachine

Problem

Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?

Solution

In my favourite definition a finite state automaton is specified as 5-tuple $(Q,\Sigma,\delta,q_0,F)$, where $Q$ is the finite set of states, $\Sigma$ is a (finite, nonempty) alphabet, $q_0\in Q$ the initial state, $F\subseteq Q$ the set of final states, and $\delta\subseteq Q\times\Sigma\times Q$ the set of transitions. In that definition we would have exactly one initial state.

It is however very well possible that, for reasons of symmetry, one specifies a set $I\subseteq Q$ of initial states. There you can have one, several, of no initial state.

Short answer: consult the book, lecture notes, or scientific paper you are using. They set the rules for the game. Not us, not wikipedia.

Context

StackExchange Computer Science Q#12338, answer score: 5

Revisions (0)

No revisions yet.