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. It is designed to automatically follow a predetermined sequence of operations. The term automata is derived from 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 that every machine takes some input. That input can have to pass through multiple stages. Every stage has some information that what to do with incoming input. It can either reject the input or returns 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.

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 item such as snacks, token, cards, newspaper and so on. It is a smart machine, more interactive to user experience and reduce cost of human efforts.

In this, users insert money, money counters send to control unit. The user chooses the product through the control unit. The Vending machine internal program dispenses the product when 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 also has implemented smart intelligent device. The automata theory is also behind this. It intelligently control vehicles and pedestrian crossing.


Video Game

The Automata technology makes video game 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 set itself.

Example
{2,32,17,49}

Set Membership ∈

It denotes the element belongs to the set.

Example
2 ∈ {2,32,17,49}

Set Nonmembership ∉

It denotes the element not belongs the set.

Example
5 ∉ {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 empty set and is denoted by Ø.




Automata Terminologies

These are some basic terminology used in automata-

Alphabets

A finite, non empty set of symbols. It is denoted by Greek letter ∑. This is the set over which the strings are defined. These are the 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 ∑12 = {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 length of the string is denoted by |w|.


Languages

A set of valid strings over a finite alphabet. It is denoted by L.
Empty Language - The empty string contains no string, denoted by {} or ∅.

Example of Language

∑ = {a,b}
L = {aa, ab, ba, bb}

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,..}




Read more articles