BASICS OF AUTOMATA THEORY FOR DUMMIES BY A DUMMY
The word Automata is derived from the Greek word automaton, which means “a moving mechanical device made in imitation of a human being”.
Automata theory got traction in 1943, Warren McCullough and Walter Pitts, two American neurophysiologists presented a paper on neural network theory called “A Logical Calculus Immanent in Nervous Activity”, this paper talked about how the human thought process can be modelled. This paper was then later generalised by G.H Mealy and E.F Moore, this generalisation led to the invention of Finite State Machines, Moore Machine and the Mealy Machine.
Automata Theory allows us to understand how machines compute and solve problems. It also allows to check if a function is computable or for a question to be decidable.
What are Automatons?
An automaton is an abstract model of a computing device which follows a predetermined sequence of operations automatically. An automata with a finite number of states is called Finite Automata(FA) or Finite-State Machine (FSM).
The Four Major Families of Finite Automaton are:
- Finite-State Machines (FSM)
- Pushdown automata
- Linear -bounded automata
- Turing machines
What are Finite State Machines?
Finite state machines are ideal computation models for a small amount of memory, and do not maintain memory (i.e store any data). This mathematical model of a machine can only reach a finite number of states and transitions between these states. A state of a finite automaton is a configuration of the dynamic entities of the underlying system. Finite State Machines are used mostly to perform mathematical problem analysis.
An elevator is a perfect example of a finite state machine. The elevator does not remember all the previous floors it has been to, it only knows the current floor it’s in and the direction of motion. This is how finite state machine behave as well. There are two types of finite state machines, Deterministic Finite State Machines and Non-Deterministic Finite State Machines.
Hold up, what are Deterministic Finite State Machines and Non-Deterministic Finite State Machines?
A Finite Automata is said to be deterministic, if corresponding to an input symbol, there is a single resultant state i.e there is only one transition.
A deterministic finite automaton (DFA) is a 5-tuple (Q,Σ,δ,q0,F), where
- Q is a finite set called the states
- Σ is a finite set called the alphabet
- δ : Q × Σ → Q is the transition function, q0 ∈ Q is the start state, and F ⊆ Q is the set of accept states.
A Finite Automata is said to be Nondeterministic, if there is more than one possible transition from one state on the same input symbol.
An NFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
- Q is a finite set of states
- ∑ is a finite set of symbols called the alphabets
- δ is the transition function where δ: Q × ∑ → 2Q
- q0 is the initial state from where any input is processed (q0 ∈ Q)
- F is a set of final state/states of Q (F ⊆ Q).
All Deterministic Finite Acceptors are Non-Deterministic Finite Acceptors but not all Non- Deterministic Finite Acceptors are Deterministic Finite acceptors.
In 1936 Alan Turing, the father of computer science conceived the first infinite model of computation, the Turing machine to solve the Entscheindungsproblem. The problem asks for an algorithm that considers, as input, a statement and answers “Yes” or “No” according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms.
The Turing machine can be thought of as a finite automaton or control unit equipped with an infinite storage. Its “memory” consists of an infinite number of one- dimensional array of cells. Turing’s machine is essentially an abstract model of modern-day computer execution and storage, developed in order to provide a precise mathematical definition of an algorithm or mechanical procedure.
Without Automata theory, modern computer’s would not exist.
References: —
