Section 12.1 Definitions and Components
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 (e.g., Turing machines and Petri nets).
A Finite-State Machine (FSM) is a computational model that has a finite set of possible states \(S\text{,}\) a finite set of possible input symbols (the input alphabet) \(X\text{,}\) and a finite set of possible output symbols (the output alphabet) \(Z\text{.}\) The machine can exist in one of the states at any time, and based on the machine’s input and its current state, it can transition to any other state and produce an output. The functions that take in the machine’s current state and its input and map them to the machine’s future state and its output are referred to as the state transition function and the output function, respectively. The default state of an FSM is referred to as the initial state.
Subsection 12.1.1 Mealy State Machine
A Mealy finite-state machine is defined by the tuple \((S, X, Z, w, t, s_0)\) where:
- \(S=\{s_0, s_1, s_2,\ldots , s_n\}\) is the state set, a finite set that corresponds to the set of all memory configurations that the machine can have at any time.
- The state \(s_0\) is called the initial state.
- \(X=\{x_0, x_1, x_2, \ldots ,x_m\}\) is the input alphabet.
- \(Z=\{z_0, z_1,z_2, \ldots ,z_k\}\) is the output alphabet.
- \(w: S\times X \to Z\) is the output function, which specifies which output symbol \(w(s, x) \in Z\) is written onto the output device when the machine is in state \(s\) and the input symbol \(x\) is read.
- \(t:S\times X \to S\) is the next-state (or transition) function, which specifies which state \(t(s, x) \in S\) the machine should move to when it is currently in state \(s\) and it reads the input symbol \(x\text{.}\)
Subsection 12.1.2 Other Types of Finite State Machines
Subsubsection 12.1.2.1 Moore Machine
In a Moore Machine, the output depends solely on the current state. Unlike Mealy state machine, this machine must enter a new state for the output to change.
A Moore machine is also represented by the 6-tuple \((S, X, Z, w, t, s_0)\) where:
- \(S=\{s_0, s_1, s_2,\ldots , s_n\}\) is the state set, and \(s_0\) is the initial state.
- The state \(s_0\) is called the initial state.
- \(X=\{x_0, x_1, x_2, \ldots ,x_m\}\) is the input alphabet.
- \(Z=\{z_0, z_1,z_2, \ldots ,z_k\}\) is the output alphabet.
- \(w: S \to Z\) is the output function, which specifies which output symbol \(w(s) \in Z\) associated with the machine current state \(s\text{.}\)
- \(t:S \times X \to S\) is the transition function, which specifies which next state \(t(s, x) \in S\) the machine should move to when its current state is \(s\) and it has the input symbol \(x\text{.}\)
Subsubsection 12.1.2.2 Finite-State Automaton
A final state (also known as the accepted state) is defined as a special predefined state that indicates whether an input sequence is valid or accepted by the finite-state machine. The set \(F\) of all final states is a subset of the states set \(S\text{.}\)
A Finite-State Automaton is a finite-state machine with no output, and it is represented by the 5-tuple \((S, X, t, s_0, F)\) where:
- \(S=\{s_0, s_1, s_2, \ldots , s_n\}\) is the state set, \(s_0\) is the initial state, and \(F\) is the set of final states.
- The state \(s_0\) is called the initial state.
- The subset \(F \subset S\) is the set of all final states of the machine.
- \(X=\{x_0, x_1, x_2, \ldots , x_m\}\) is the input alphabet.
- \(t: S \times X \to S\) is the transition function, which specifies which next state \(t(s, x) \in S\) the machine should move to when its current state is \(s\) and it has the input symbol \(x\text{.}\)
When the state machine processes a finite input sequence, it transitions through various states based on each input in the sequence and the current state of the machine. If, after processing the entire sequence, the machine lands in any of the final states, then the input sequence is considered valid (or recognized according to the machine’s rules). Otherwise, the input sequence is rejected as invalid.
Subsubsection 12.1.2.3 Deterministic Finite Automaton (DFA)
A Deterministic Finite Automaton (DFA) is a simplified automaton in which each state has exactly one transition for each input. DFAs are typically used for lexical analysis, language recognition, and pattern matching.
Subsubsection 12.1.2.4 Nondeterministic Finite Automaton (NFA)
Unlike a DFA, an NFA allows multiple transitions for the same input or even transitions without consuming input (\(\epsilon\)-transitions).
Subsubsection 12.1.2.5 Turing Machine
A Turing Machine is an expansion of an FSM, which includes infinite tape memory representing both the input and output streams (shared stream). Unlike all other FSMs, a Turing machine can alter the input/output stream, and as such, it is capable of simulating any algorithm. Turing machines are the theoretical foundation for modern computation (any general-purpose computer executing any algorithm can be modeled as a Turing Machine).
Finite state machines are a foundational concept in computer science, often associated with tasks related to system designs (circuits and digital computers, algorithms, etc.). However, the vast and rich domain of applications of state machines extends far beyond simple simulations to the full control logic of complex industrial processes and workflows. These tasks can vary in complexity, ranging from a simple parity check to managing traffic patterns, a programming language compiler, or natural language recognition and processing.
State machines offer a structured way to model systems with discrete states and transitions. Different variants, such as the Mealy machine and Moore machine, have distinct characteristics and, as such, can adapt to various applications.
