In The Name of
Allah the Most
Merciful and
Beneficent
Theory of
Computation
Course Instructor: Dr. Zobia Suhail
Theory of Computation
• Theory of Computation, is a field within computer
science and mathematics that focuses on studying
abstract machines to understand the capabilities and
limitations of computation by analyzing mathematical
models of how machines can perform calculations.
• How efficiently problems can be solved on a model of
computation, using an algorithm
Theory of Computation
• Core Areas of Theory of Computations:
This field is divided into three major branches:
• Automata Theory of Language
• Computability Theory
• Computational Complexity Theory (Efficiency)
Theory of Computation
• Core Areas of Theory of Computations:
This field is divided into three major branches:
What are fundamental
• Automata Theory of Language capabilities and
limitations of
• Computability Theory computers
• Computational Complexity Theory (Efficiency)
Theory of Computation
• Core Areas of Theory of Computations:
Automata Theory of Language:
Automata theory deals with definitions and properties of
different types of “computational models”.
• Finite Automata
• Context-Free Grammars
• Turing Machines
Theory of Computation
• Core Areas of Theory of Computations:
Automata Theory of Language:
Automata theory deals with definitions and properties of different
types of “computational models”.
• Finite Automata : Used in text processing, compilers and
hardware designs
• Context-Free Grammars
• Turing Machines
Theory of Computation
• Core Areas of Theory of Computations:
Automata Theory of Language:
Automata theory deals with definitions and properties of different
types of “computational models”.
• Finite Automata : Used in text processing, compilers and
hardware designs
• Context-Free Grammars: Used to define programming languages.
• Turing Machines:
Theory of Computation
• Core Areas of Theory of Computations:
Automata Theory of Language:
Automata theory deals with definitions and properties of different types
of “computational models”.
• Finite Automata : Used in text processing, compilers and hardware
designs
• Context-Free Grammars: Used to define programming languages.
• Turing Machines: A simple abstract model of a “real” computer, such
as PC
Theory of Computation
• Core Areas of Theory of Computations:
Automata Theory of Language:
? DO these models have same power, or can one model
solve more problems
Then the other?
Theory of Computation
• Core Areas of Theory of Computations:
Computability Theory:
In the 1930’s, Godel, Turing and Church discovered that some of the
fundamental mathematical problems cannot be solved by a computer
To attack such a problem, we need formal definition of the notions of
computer, algorithm, and computation.
The theoretical models that were proposed in order to understand
solvable and unsolvable problems led to the development of real
computers.
Theory of Computation
• Core Areas of Theory of Computations:
Computability Theory:
? CLASSIFY problem as being solvable or unsolvable?
Theory of Computation
• Core Areas of Theory of Computations:
Complexity Theory:
Main question asked in this area “What makes some problems
computationally
hard and other problems easy?”
A problem is called easy if it is efficiently solvable: Sorting a number , finding
a name in telephone directory
A problem is said to be hard if it can not be solved efficiently or if we don’t
know whether it can be solved efficiently: Factoring 300-digit number to its
prime factors
Theory of Computation
• Core Areas of Theory of Computations:
Complexity Theory:
? CLASSIFY problems according to their degree of “difficulty”.
Give a proof that problems that seem to be “hard” are really “hard”
Theory of Computation
• Purpose and Motivation:
What are mathematical properties of computer hardware
and software?
What is a computation and what is an algorithm ?
Can we give mathematical definitions of these notions?
What are the limitations of computers? Can “everything” be
computed?
Theory of Computation
• Purpose and Motivation:
“Develop formal mathematical models of computation that
reflect
real-world computers”
Theory of Computation
• Basic Terminologies:
Let’s understand the basic terminologies, which are
important and frequently used in the Theory of
Computation.
Theory of Computation
• Basic Terminologies:
Let’s understand the basic terminologies, which are
important and frequently used in the Theory of
Computation.
• 1. Symbol
• A symbol (often also called a character) is the smallest
building block, which can be any alphabet, letter, or
picture.
Theory of Computation
• Basic Terminologies:
2. Alphabets (Σ)
• A finite, non-empty set of symbols used to construct
strings and languages. For example, Σ = {a, b}.
Theory of Computation
• Basic Terminologies:
• 3. String
• 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 with zero occurrence of symbols, represented as ε.
Theory of Computation
• Basic Terminologies:
• 3. StringNumber of Strings (of length 2)
that can be generated over the alphabet {a, b}:
––
aa
ab
ba
bb
Length of String |w| = 2
Number of Strings = 4
Conclusion:
For alphabet {a, b} with length n, number of
strings can be generated = 2n.
Theory of Computation
• Basic Terminologies:
• 3. Reverse of String
Reverse of a string W , written WR is the string obtained by
writing W in
The opposite order (i.e. wn, wn-1,…. w1)
Theory of Computation
• Basic Terminologies:
• 3. Substring of String
String z is a substring of W if z appears consecutively within
W.
Example:
cad is a substring of aascdhcadhhhjjcbdg
Theory of Computation
• Basic Terminologies:
Lexicographic Ordering of Strings
Lexicographic Ordering of Strings is the same as the familiar
dictionary ordering, except that shorter strings precede
longer strings. Thus the Lexicographic ordering of all strings
over the alphabet {0,1} is
(ε, 0 , 1, 00, 01, 10, 11, 000, …)
A language is a set of strings.
Theory of Computation
• Basic Terminologies:
Closure Representation in TOC
1. L+: It is a Positive Closure that represents a set of all strings except Null
or ε-strings.
2. L*: It is “Kleene Closure“, that represents the occurrence of certain
alphabets for given language alphabets from zero to the infinite number of
times. In which ε-string is also included.
From the above two statements, it can be concluded that:
Theory of Computation
• Basic Terminologies:
Closure Representation in TOC
1. L+: It is a Positive Closure that represents a set of all strings except Null
or ε-strings.
2. L*: It is “Kleene Closure“, that represents the occurrence of certain
alphabets for given language alphabets from zero to the infinite number of
times. In which ε-string is also included.
From the above two statements,L* = εL
it can be +concluded that:
Theory of Computation
• Basic Terminologies:
Closure Representation in TOC
Example:
a) Regular expression for language accepting all combination of g’s over Σ={g}:
R = g*
b) Regular Expression for language accepting all combination of g’s over Σ={g} :
R = g+
Theory of Computation
• Basic Terminologies:
Closure Representation in TOC
Example:
a) Regular expression for language accepting all combination of g’s over Σ={g}:
R = g*
R={ε,g,gg,ggg,gggg,ggggg,…}
b) Regular Expression for language accepting all combination of g’s over Σ={g} :
R = g+
R={g,gg,ggg,gggg,ggggg,gggggg,…}
Theory of Computation
• Basic Terminologies:
Closure Representation in TOC
Note: Σ* is a set of all possible strings
So this implies that language is a subset of Σ*.This is also called a “Kleene Star”.
Theory of Computation
• Basic Terminologies:
Language
•A language is a set of strings formed using the symbols of a given
alphabet Σ.
•Formally, a language is a subset of Σ∗, where Σ∗ is the set of all possible
strings (including ε) over the alphabet Σ.
Theory of Computation
• Basic Terminologies:
Language
Examples:
Finite Language:
Infinite Language:
Theory of Computation
• Basic Terminologies:
Language
Examples:
Finite Language:
L1 = { set of string of 2 }
L1 = { xy, yx, xx, yy }
Infinite Language:
Theory of Computation
• Basic Terminologies:
Language
Examples:
Finite Language:
L1 = { set of string of 2 }
L1 = { xy, yx, xx, yy }
Infinite Language:
L1 = { set of all strings starts with ‘b’ }
L1 = { babb, baa, ba, bbb, baab, ……. }
Theory of Computation
• Basic Terminologies:
Types of Languages in TOC
Languages are classified based on the computational model or grammar
generating them:
Regular Languages: Defined using regular expressions or finite
automata. Example: L=an∣n≥0.
Context-Free Languages: Defined using context-free grammars or
pushdown automata. Example: L=anbn∣n≥0.
Context-Sensitive Languages: Defined using context-sensitive
grammars or linear-bounded automata.
Recursive and Recursively Enumerable Languages: Defined using
Turing machines that enumerate all valid strings of a machine.
Theory of Computation
• Basic Terminologies:
Types of Languages in TOC
Languages are classified based on the computational model or grammar
generating them:
Regular Languages: Defined using regular expressions or finite
automata. Example: L=an∣n≥0.
Context-Free Languages: Defined using context-free grammars or
pushdown automata. Example: L=anbn∣n≥0.
Context-Sensitive Languages: Defined using context-sensitive
grammars or linear-bounded automata.
Recursive and Recursively Enumerable Languages: Defined using
Turing machines that enumerate all valid strings of a machine.
Theory of Computation
• Graphs:
• Boolean Logic
End of Lecture # 1.
