LECTURE NOTES
Subject: Theory of Computation Unit-1: Introduction
_______________________________________________________________________________________________
What is Theory of Computation?
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.
It provides the mathematical model for any machine and it also ensures how efficiently a machine
will work, what are its limitations and how much amount of memory it requires to perform
operations.
The main motivation behind developing this theory was to develop methods to describe and
analyse the dynamic behaviour of discrete systems.
Types of Mathematical models:
Basically, there are 3 types of mathematical models covered in Theory of Computation as shown in diagram.
1. Finite Automata
2. Push Down Automata
3. Turing Machine
Finite Automata:
It is the simplest mathematical model and is the basic building block of machine.
It performs the low memory operations. e.g. pattern matching in Compiler Design
It accepts Regular language that uses Regular Grammar
Prepared by: Mr. Dinesh A Mehbubani
(CE/IT Department, LJ University, Ahmedabad)
LECTURE NOTES
Subject: Theory of Computation Unit-1: Introduction
_______________________________________________________________________________________________
Push Down Automata:
It is more powerful than Finite Automata.
It performs the operations like Syntax verification in high end applications.
It accepts Context Free language that uses Context Free Grammar.
Turing Machine:
It is the most powerful mathematical model to design any machine.
It is considered to be the abstract model of a computer.
It was invented by mathematician Allen Turing in 1936.
It uses unrestricted language also known as recursively enumerable language.
It performs the operations such as halting problems in Compiler designing.
Basic Terminologies of Theory of Computation:
Symbol:
A symbol (often also called a character) is the smallest building block, which can be any alphabet,
letter, or picture.
Alphabets (Σ):
Alphabets are a set of symbols, which are always finite.
String: (w)
A string is a finite sequence of symbols from some alphabet. A string is generally denoted as w and
the length of a string is denoted as |w|.
Empty string is the string zero occurrence of symbols, represented as ε.
Number of Strings (of length 2) that can be generated over the alphabet {a, b}:
Prepared by: Mr. Dinesh A Mehbubani
(CE/IT Department, LJ University, Ahmedabad)
LECTURE NOTES
Subject: Theory of Computation Unit-1: Introduction
_______________________________________________________________________________________________
a a
a b
b a
b b
Length of String |w| = 2
Number of Strings = 4
For alphabet {a, b} with length n, number of strings can be generated = 2n.
Language: (L)
A language is a set of strings, chosen from some Σ . A language that can be formed over ‘Σ ‘can
be finite or infinite.
Example of Finite Language:
L1 = {set of string of length 2 from ∑(x,y)}
L1 = { xy, yx, xx, yy }
Example of Infinite Language:
L1 = {set of all strings starts with ‘b’}
L1 = { babb, baa, ba, bbb, baab, ....... }
Prepared by: Mr. Dinesh A Mehbubani
(CE/IT Department, LJ University, Ahmedabad)
