Introduction: Theory of Computation | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Definition - Theory of Computation

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

Theory Of ComputationSome more points regarding the theory of computation: 

• Automata* enables the scientists to understand how machines compute the functions and solve problems. 
• The main motivation behind developing Automata Theory was to develop methods to describe and analyse the dynamic behavior of discrete systems.
• The field is divided into three major branches: automata theory, computability theory and computational complexity theory. 
• In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. 
• Automata is originated from the word “Automaton” which is closely related to “Automation”.
• This automaton consists of:
  1. states (represented in the figure by circles),
  2. transitions (represented by arrows). 
• As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs). Uses of Automata: compiler design and parsing.
   

Basics of Formal Language Theory

Our view of languages is that a language is a set of strings. In turn, a string is a finite sequence of letters from some alphabet. These concepts are defined rigorously as follows.

1. Symbol: 

Symbol is the smallest building block, which can be any alphabet, letter or any picture.

2. Alphabets (Σ): 

3. String: 

Empty string is the string with zero occurrence of symbols, represented as ε.

Number of Strings (of length 2) that can be generated over the alphabet {a, b} -

Length of String |w| = 2

Number of Strings = 4

Conclusion:
For alphabet {a, b} with length n, number of strings can be generated = 2ⁿ.
Note: If the number of Σ’s is represented by |Σ|, then number of strings of length n, possible over Σ is |Σ|ⁿ. 

4. Language: 

5. Powers of ‘Σ‘:

Say Σ = {a,b} then
Σ⁰ = Set of all strings over Σ of length 0. {ε}
Σ¹ = Set of all strings over Σ of length 1. {a, b}
Σ² = Set of all strings over Σ of length 2. {aa, ab, ba, bb}
i.e. |Σ²|= 4 and Similarly, |Σ³| = 8
Σ* is a Universal Set.
Σ* = Σ⁰ U Σ¹ U Σ² ..........
= {ε} U {a, b} U {aa, ab, ba, bb}
= .............   //infinite language

6. Convention: