Systems Analysis and Synthesis

3.2. Deterministic and Non-deterministic Automata

To illustrate some basic properties of finite-state automata , let us consider a simple problem: to determine whether the parity of a stream of binary digits is even (i.e., contains an even number of 1’s). Figure 3.3 is the state-transition diagram of such an automaton. It has two states, labelled Even and Odd. It starts in the Even state. On an input of 1 it always changes state, but on an input of 0 its state doesn’t change. If at the end of the input sequence it is in the Even state, the parity is even; if it is in the Odd state, the parity is odd. Since the goal here is to detect if the input has even parity, the Even state is its final state.⁵

FIGURE 3.3 A state-transition diagram of an FSA ...