Section 11.1 Finite-State Machines
The defining feature of any abstract machine is its memory structure, ranging from a finite set of states in the case of finite-state machines to more complex memory systems (Turing machines).
A Finite-State Machine (FSM) has an input device (that physically could represent a tape, data stream, memory space ...etc), divided into segments, each holding an instruction symbol or a blank. This abstract machine also has a read head that scans the current symbol from the input alphabet \(X\text{.}\) After each read, the head always moves to the next segment. The machine may also have an output device, with symbols drawn from an output alphabet \(Z\text{,}\) which may differ from the input alphabet.
Subsection 11.1.1 Definition
A finite-state machine is defined by a sextuple \((S, X, Z, w, t, s_1)\) where:
- \(S=\{s_1, s_2,\ldots , s_r\}\) is the state set, a finite set that corresponds to the set of memory configurations that the machine can have at any time, where \(s_1\) is the initial state.
- \(X=\{x_1, x_2, \ldots ,x_m\}\) is the input alphabet.
- \(Z=\{z_1,z_2, \ldots ,z_n\}\) is the output alphabet.
- \(w: X\times S \to Z\) is the output function, which specifies which output symbol \(w(x, s) \in Z\) is written onto the output device when the machine is in state \(s\) and the input symbol \(x\) is read.
- \(t:X\times S\to S\) is the next-state (or transition) function, which specifies which state \(t(x, s) \in S\) the machine should enter when it is in state \(s\) and it reads the symbol \(x\text{.}\)
