Section 1.3: What is the Automata Theory and its models?

Definition

The Computational Automata Theory is a part of the Theory of Computation that studies the abstract machines; abstract machines are mathematical models that could be utilized for modelling the computational algorithms. At the core level, they comprise automata states, transitional functions, and a set of input alphabets. Some machines add more elements to their automaton definition and introduce memory items (e.g., Push down stacks and Linear buffers).

The computational automata theory is used in compiler engineering, machine learning, game development, and embedded systems to build language recognizers, and state management systems. An automaton A is said to accept a particular language L (i.e., set of alphabets) if and only if; there exists at least one automaton \(A' \subseteq A\) that has valid state transitions for a subset of the defined alphabets \(L' \subseteq L\) (i.e., the alphabet for that language).
This document will redefine the automata theory for systems engineering, and will attempt to forge it with the SES/MB framework, previously examined in Section-1.2.

Types of the Automata Models

An Automaton is represented formally using a sequence of 5+ tuple; a tuple is an element cell in a sequence structure; a sequence is an ordered elementary structure. 1 Of which, main elements are \(Q\) a set of states; \(\Sigma\) a set of input alphabets; \(\delta\) transitional function transiting from a state to another with an input; \(q_0\) the start or the initial state; \(F\) a set of final states at which the automata could accept (i.e., finalize).

Here is a brief list of the famous types of the automata models:

  1. Finite-state Automaton (FSA): is an abstract mathematical machine that consists of a finite number of states. It includes a start state \(q_0\) in which the machine is in initially; a finite set of states Q; an input alphabet ; a state transition function \(\delta\), and a set of final accepting states F (where \(F \subseteq Q\)). 2

    FSA

  2. Push-down Automaton (PDA): is defined formally as a 7-tuple sequence \((\Sigma, Q, \Gamma, \delta, q_0, Z, F)\). The set \(\Sigma\) is a finite set which is called the input alphabet; the set Q is a finite set of states; is the set of stack symbols; is the transition function which maps \(Q \times \{\Sigma \cup \{\epsilon\}\} \times \Gamma\) into finite subsets of \(Q \times \Gamma^{*2}\); where \(\Gamma^{*2}\) represents a double closure that is a subset of the stack \(\Gamma\); \(q_0\) is the initial state; Z is the initial stack top symbol on the stack (i.e. \(Z \in \Gamma\)), and F is the set of accepting states (i.e. \(F \subseteq Q\)). 3

    PDA

  3. Turing Machines: is defined formally as a 7-tuple \(M = (Q, \Gamma, b, \Sigma, \delta, q_0, F)\); \(Q\) is a finite set of states; \(\Gamma\) is a finite set of the tape alphabet/symbols; \(b \in \Gamma\) is the blank symbol (This is the only symbol that is allowed to occur infinitely often on the tape during each step of the computation); \(\Sigma\) is the set of input symbols and is a subset of \(\Gamma\) (i.e. \(\Gamma = \Sigma \cup \{ b \}\)); \(\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}^*\) is the transition function. This is a partial function where \(L\) is left shift and \(R\) is right shift; \(q_0 \in Q\) is the initial state; \(F \subseteq Q\) is the set of final or accepting states. 4

  4. Hybrid Automata: are digital real-time systems embedded in analog environments such as a digital embedded control program for an analog plant environment. The controller state moves discretely between the control modes, and within each control mode the plant state evolves continuously according to physical laws. 5

Partial Functions: A partial function (or partial mapping) may be undefined for some values of the function domain (i.e., for all values in the domain, there exists at least one value in the range that is undefined), and partial functions arise regularly in the computing field. Total functions, on the other hand, are defined for every value in the function domain (i.e., for all values in the domain, there exists only one value in the range), and many functions encountered in mathematics are total. 6

The jME Architectural Documentation and the Automata Theory

This mini-book will attempt to use a blend of the PDA and the Turing Machines forged into the SES/MB structure to link jME system behavior to its subsystems structure. The final architecture should give developers an idea of how and why things exist as they are now, and their functionalities and their interrelations in depth.

References