Introduction to Automata Theory | Introduction of Theory of Computation

Automata theory (also known as Theory of Computation) is a theoretical branch of Computer Science and Mathematics.  It deals with the logic of computation with respect to simple machines, referred to as automata. 

Theory of computation deals with how efficiently problems can be solved on a model of computation using algorithm.

 

Automata theory is the study of abstract machines (computing device) and the problems they are able to solve. The abstract machine is called the automata. Automata enable scientists to understand how machines compute the functions and solve problems

 

Automata theory is basically about the study of different mechanisms for generation and recognition of languages. Automata theory is basically for the study of different types of grammars and automata. A grammar is a mechanism for the generation of sentences in a language. Automata is a mechanism for recognition of languages. Automata theory is mainly for the study of different kinds of automata as language recognizers and their relationship with grammars.

 

Automata is the study and understanding of abstract machines. Automata deals with logical computation, with the basic theories regarding automata helping scientists figure out how machines solve and compute problems.

An automaton is a machine that is relatively self-operating, following a predetermined sequence of instructions and operations. The automaton consists of states and transitions. The State is represented by circles, and the Transition is represented by arrows.An automaton with a finite number of states is called a Finite automaton (FA) or Finite State Machine (FSM).

An Automata is a self-operating machine that is designed to respond to and follow specific instructions. Automata is considered the plural of automaton. It is set up or programmed to follow a prescribed set of instructions or sequencing.

Automata is the kind of machine which takes some string as input and this input goes through a finite number of states and may enter in the final state.

In simple terms, the Theory of Computation answers these questions:

• What problems can the machine solve? What problems can’t it solve?
• How fast can a machine solve a problem?
• How much memory space does a machine need to solve a problem?

To answer these questions, computer scientists use a model of computation, which is a computer simulation for the algorithm being developed. The Turing machine is among the most used models of computation.

How Does Automata Work?

Automata works when it is given a particular set of orders, distinct facts, or what are often called inputs. Inputs are the sequences of symbols that are selected from a finite set of input signals. The automaton will then work a prescribed or predetermined way each time. Different automata will perform their functions in different ways, depending on the type. 

There are four specific areas or types of automaton. They include the following:

Finite State Machine: Finite state machines are computation models that are ideal for a small amount of memory. They also don’t maintain memory. The primary application is in regards to mathematical problem analysis. A finite state machine is considered the simplest of all types of automata.

Pushdown Machine: These are finite state machines that are augmented with extra memory in what is called a stack. New elements are pushed into the stack. These machines can do more than a finite machine, but not as much as a Turing machine.

Turing Machine: This type of automata is the most advanced. It is capable of changing symbols and simulating computer storage and execution. High performance computing, machine learning, and software testing are examples that involve the complexity of Turing machines. Turing machines were one of the first foundational models that led to what is modern computer science.

Linear Bounded: This is considered a restricted type of Turing machine. Computation is restricted and operates within a finite, bounded area.

The Basic Terminologies frequently used in the Theory of Computation:

Symbols: It is the smallest building block, which can be any alphabet, letter, or picture. 

Example:   { a,b,c,0,1,2,3,……}

Alphabet: Alphabets are a finite set of symbols. It is denoted by ∑ (sigma).

Example:

Alphabet set for binary numbers ∑= {0,1}

Alphabet set for decimal numbers ∑= {0, 1,…, 9}

Set of all lower case letters ∑= {a,b,c,….z}

Alphabet set for English language ∑= { A, B, …, Z, a, b, …, z }

 

String: A string or word is a finite set of symbols chosen from some alphabet. A string is generally denoted as w and the length of a string is denoted as |w|.

Example:

∑ = {0,1}, string that can be generated from this alphabet are {0, 1, 11, 00, 01101 ,….}

∑ = {a, b}, various string that can be generated from this alphabet are: {a, b, aa, ab, ba, bb, aaa, bb, bbb, ba, aba.....}.

 

Empty string: String with zero symbol. An empty string, denoted by e, is a string containing no symbol.

A string with zero occurrences of symbols is known as an empty string or null string. It is denoted by ε (epsilon) or λ (lambda).

Length of a string: The number of symbols in a string w is called the length of a string. It is denoted by |w|.

Example:

∑ = {0,1}

w = 01011     |w|= |01011|=5

If w=ε ,  then |w|=0       

 

Powers of an Alphabet: ∑k is the set of strings of length k chosen from ∑.

∑⁰={ ε}

∑ ¹={0,1}

∑ ²={00,01,10,11}

∑ ³={000,001,010,011,100,101,110,111}

………………..

 Set of all strings over an alphabet ∑,

 ∑*=∑⁰U∑ ¹U∑ ²U……

{0,1}*={ ε,0,1,00,01,10,11,…….}

 

Concatenation of the strings:

x=110         y=001

xy=110001

yx=001110

Language: A language is a set of strings or words chosen from some ∑* or we can say -A language is a subset of ∑* . A language that can be formed over ‘ Σ ‘ can be Finite or Infinite. It is denoted by L.

 

·   Φ denotes empty language.

·   { ε} language consist of  empty string.

Example:

Set of binary numbers whose value is a prime.

L={10,11,101,111,….}

Language of all strings consisting of n 0’s followed by n 1’s, for some n>=0:

L={ ε,01,0011,000111,….}

Set of strings of 0’s and 1’s with equal number of each
L={ ε,01,10,0011,0101,1010,…}

Example of Finite Language:
L1 = { set of string of length 2 }
L1 = { aa,ab,ba,bb }

Example of Infinite Language:
L1 = { set of all strings starts with 'a' }
L1 = { a,aa,aaa,ab,aab,aba,abb ....... }