Automata Theory
Automaton, in plural Automatons or Automata, is a self-operating device. Automata Theory lies in Computer Science and Discrete Mathematics. It is the study of the abstract machine in theoretical computer science. It is designed to automatically follow a predetermined sequence of operations. The term automata is derived from the Greek word αὐτόματα, which means 'self-making'. It means it automatically processes the production of specific work.
Automata Inventor
The Jacques de Vaucanson was responsible for the invention of innovative and impressive Automata.
As all of us know, every machine takes some input. That input can have to pass through multiple stages. Every stage has some information on what to do with the incoming input. It can either reject the input or return some output. So, that needs computation of the machine. This is the basic concepts behind Automata Theory.
Characteristics of Automata
The basic characteristics of automata include the following:
- Inputs - It is a finite set of input symbols or sequences of symbols, {x1, x2, x3,...xk}, where k is the number of inputs.
- Outputs - It is a finite set of output symbols, {y1, y2, y3,...ym}, where m is the number of outputs.
- States - It is a finite set, denoted by Q whose definition depends on the type of automaton.
Examples of Automata Machine
The formal definition of everything is not making sense until we know the real-life examples. These are some fields where Automata theory is applied.
Vending Machine
A vending machine is an automated machine that accepts money either from cash, credit card or debit card and provides items such as snacks, tokens, cards, newspaper and so on. It is a smart machine, more interactive to user experience and reduces the cost of human efforts.
In this, users insert money, money counters send to the control unit. The user chooses the product through the control unit. The vending machine internal program dispenses the product when the correct amount is inserted. It depends on the design of Finite State Machine (FSM) and Visual Automata Simulator (VAS) method.
Traffic Light
Today, traffic control system has also implemented a smart intelligent device. The automata theory is also behind this. It intelligently control vehicles and pedestrian crossing.
Video Game
The Automata technology makes video games more adaptive, responsive and intelligent. The power of automata makes representing players with strategies. The most popular automata theory widely used in game theory is finite automata, adaptive automata and cellular automata.
Compiler
Automata theory is used in the phase of the compiler. In a compiler, source code is converted to target code in six phases. The lexical analysis is used in the first phase. It reads the input character by character until finding the lexeme. After that, it parses the code in DFA (Deterministic Finite Automata).
Basic Mathematical Terminology used in Automata
Before knowing the Automata terminology, let's know the basic mathematical terminology that's mostly used in Automata.
Set
A set is a group of objects containing symbols, numbers, objects and even the set itself.
Example{2,32,17,49}
Set Membership ∈
It denotes the element belongs to the set.
Example2 ∈ {2,32,17,49}
Set Nonmembership ∉
It denotes the element that does not belong to the set.
Example5 ∉ {2,32,17,49}
Subset ⊆
If A and B are two sets, we say that A is a subset of B, A⊆B, if every element of A is also element of B.
Example{3,9,12} ⊆ {3,9,12}
Proper Subset ⊂
If A and B are two sets, we say that A is a proper subset of B, A ⊂ B, if A is a subset of B and not equal to B.
Example{5,24} ⊂ {5,24,43}
Empty Set Ø
A set with 0 elements is called an empty set and is denoted by Ø.
Automata Terminologies
These are some basic terminology used in Automata Theory.
Alphabets
A finite, non-empty set of symbols is known as Alphabet. It is denoted by Greek letter ∑. This is the set over which the strings are defined. These are some examples of alphabets.
Examples of Alphabets
∑ = {a,b,c,d}
∑ = {A,B,C} // It is an alphabet
∑ = {0,1,2,3} // It is an alphabet of digits
∑ = {0,1,a,b,c,d} // It is an alphabet of digits
Strings
A string over an alphabet is a finite sequence of any symbol selected from the set of alphabet symbols. It is generally denoted by w.
Examples of Strings
∑1 = {0,1}
w = 100111 // It is a string over an alphabet ∑1
∑2 = {a,b,c}
w2 = abaccab // It is a string over an alphabet ∑2
An empty string is denoted by as є or λ.
Length of string
- The number of symbols present in the string is known as the Length of the string. The length of the string is denoted by |w|. For the string S = 'adadda', the length of the string is |S| = 6.Languages
A set of valid strings over a finite alphabet. It is denoted by L. Language can be finite or infinite.
Empty Language - The empty string contains no string, denoted by {} or ∅.
Example of Language
∑ = {a,b}
L = {aa, ab, ba, bb}
Here, the language takes all the possible strings of length 2 over the set Σ = {a, b}
Kleene Closure
The set ∑+ is the infinite set of all possible strings of all possible length over ∑. It is generated by concatenating arbitrary elements of a set of strings. It is also called Positive Closure or Kleene Star.
Examples of Kleene Closure
∑ = {a,b}
∑* = {a, b aa, ab, ba, bb,..}
∑1 = {ab,c}
∑1* = {ab, c, abc, abab, cc, abababc,..}
Automata Set Theory