Introduction to Theory of Computation- Automata

Theory of Automata

Theory of automata is a theoretical branch of computer science and mathematical. It is the study of abstract machines and the computation problems that can be solved using these machines. The abstract machine is called the automata. The main motivation behind developing the automata theory was to develop methods to describe and analyse the dynamic behaviour of discrete systems.

This automaton consists of states and transitions. The State is represented by circles, and the Transitions is represented by arrows.

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.

There are the basic terminologies that are important and frequently used in automata:

Symbols:

Symbols are an entity or individual objects, which can be any letter, alphabet or any picture.

Example:

1, a, b, #

Alphabets:

Alphabets are a finite set of symbols. It is denoted by ∑.

Examples: 

∑ = {a, b}  
  
∑ = {A, B, C, D}  
  
∑ = {0, 1, 2}  
  
∑ = {0, 1, ....., 5]  
  
∑ = {#, β, Δ}   

String:

It is a finite collection of symbols from the alphabet. The string is denoted by w.

Example 1:

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

• A string with zero occurrences of symbols is known as an empty string. It is represented by ε.
• The number of symbols in a string w is called the length of a string. It is denoted by |w|.

Example 2:

w = 010  
  
Number of Sting |w| = 3  

Language:

A language is a collection of appropriate string. A language which is formed over Σ can be Finite or Infinite.

Example: 1

L1 = {Set of string of length 2}

     = {aa, bb, ba, bb}          Finite Language

Example: 2

L2 = {Set of all strings starts with 'a'}

     = {a, aa, aaa, abb, abbb, ababb}         Infinite Language