Theory of Computation
•Theory of Computation is the branch that deals with
whether and how efficiently problems can be solved on a
model of computation using an algorithm.
CAPP C12: Introduction to Theory of Computation Slide Number 1
Theory of Computation
•Theory of Computation has three major branches. They
are
•Automata Theory
•Computability Theory
•Computational Complexity Theory
CAPP C12: Introduction to Theory of Computation Slide Number 2
Models of Computation
•In computability theory and computational complexity
theory, a model of computation is the definition of the set
of allowable operations used in computation and their
respective costs.
CAPP C12: Introduction to Theory of Computation Slide Number 3
Models of Computability
•It is used for measuring the complexity of an algorithm in
execution time and / or memory space; by assuming a
certain model of computation, it is possible to analyze the
computational resources required or to discuss the
limitations of algorithms or computers.
CAPP C12: Introduction to Theory of Computation Slide Number 4
Automata
•Automata means to automate or mechanize.
•Mechanization is the process of performing it on a
machine without human intervention.
•Automation is a machine that can perform the
computation in mechanized way.
CAPP C12: Introduction to Theory of Computation Slide Number 5
Automata …
•An automation is defined as a system where information
and materials are transformed, transmitted and utilized for
performing some processes without direct involvement of
human.
•Automata Theory is a branch of computer science that
deals with designing abstract self propelled computing
devices that follow a predetermined sequence of
operations automatically.
CAPP C12: Introduction to Theory of Computation Slide Number 6
Automata …
•An automaton with a finite number of states is termed as
Finite Automaton and the corresponding machine is
termed as Finite State Machine.
•An automaton with a infinite number of states is termed as
Infinite Automaton and the corresponding machine is
termed as Infinite State Machine.
CAPP C12: Introduction to Theory of Computation Slide Number 7
Automata …
•The machine M take five arguments. They are
•Q=Finite Set of States
•∑= Finite Set of Symbols i.e. Alphabet
•δ= Finite Set of Transitions
•q0= Initial State
•F= finite set of final states
CAPP C12: Introduction to Theory of Computation Slide Number 8
Automata …
•F i.e. “qf ” is a set of final state/states of Q (F ⊆ Q).
•M =(Q={q0, q1, q2, qf}, ∑={0,1}, δ={δ(q0, 0 |1 , q1), δ(q1, 1|0
, q2), δ(q2, 0|1 , qf)}, q0, F={qf})
0|1 1|0 0|1
qo q1 q2 qf
CAPP C12: Introduction to Theory of Computation Slide Number 9
Automata …
State Input 0 Input 1
→qo q1 …..
q1 ….. q2
q2 qf …..
qf ….. …..
0|1 1|0 0|1
qo q1 q2 qf
CAPP C12: Introduction to Theory of Computation Slide Number 10
Automata …
State Input 0 Input 1
→qo q1 q1
q1 q2 q2
q2 qf qf
qf ….. …..
CAPP C12: Introduction to Theory of Computation Slide Number 11
Terminologies Associated with Automation
•Alphabet
•String
•Length of a String
•Kleene Star
•Kleene Closure / Plus
•Language
CAPP C12: Introduction to Theory of Computation Slide Number 12
Alphabet
•An alphabet is defined as finite set of symbols.
•Let us consider the following example
•∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’
are symbols.
CAPP C12: Introduction to Theory of Computation Slide Number 13
String
•A string is defined as a finite sequence of symbols taken
from ∑.
•Let us consider the following example
•‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}
CAPP C12: Introduction to Theory of Computation Slide Number 14
Length of String
•It is the number of symbols present in a string.
•Let “S” be a string, the length of the string S is denoted by
|S|.
•Let us consider the following example
•If S = ‘cabcad’, |S|= 6
•If |S|= 0, it is called an empty string.
•An empty string is denoted by λ or 𝝐.
CAPP C12: Introduction to Theory of Computation Slide Number 15
Kleene Star
•The Kleene star i.e. * is defined as a unary operator on a
set of symbols or strings, ∑, that gives the infinite set of all
possible strings of all possible lengths over ∑ including λ.
•The Kleene Star over the alphabet ∑ is represented as ∑* =
∑0 ∪ ∑1 ∪ ∑2 ∪……. where ∑p is the set of all possible
strings of length p.
CAPP C12: Introduction to Theory of Computation Slide Number 16
Kleene Star …
•Let us consider the following example
•If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,aaa,bbb,abb,aab,}
a|b
q0
CAPP C12: Introduction to Theory of Computation Slide Number 17
Kleene Closure
•The Kleene Closure i.e. + is defined as the infinite set ∑+ of
all possible strings of all possible lengths over ∑ excluding
λ.
•The Kleene Star over the alphabet ∑ is represented as ∑+ =
∑1 ∪ ∑2 ∪ ∑3 ∪…….
•Thus ∑+ = ∑* − { λ }
•Let us consider the following example
•If ∑ = { a, b } then ∑+ = { a, b, aa, ab, ba, bb,………..}.
CAPP C12: Introduction to Theory of Computation Slide Number 18
Language
•Language is nothing but the set of strings framed using the
alphabet of the language.
CAPP C12: Introduction to Theory of Computation Slide Number 19
Basic Operations on Language
•There are operations on languages that are common.
•They are
•Union / Concatenation
•Intersection
•Complement
•Kleene Star
•Kleene Closure
CAPP C12: Introduction to Theory of Computation Slide Number 20
Basic Operations on Language …
•They are …
•String Homomorphism
•ϵ free String Homomorphism
•Substitution
•Inverse Homomorphism
•Reverse
CAPP C12: Introduction to Theory of Computation Slide Number 21
Basic Operations on Language …
•Let L1 and L2 are languages over common alphabet ∑, then
•Concatenation of L1 and L2 consists of all strings of the
form “nm”, where string n belongs to Language L1 and
string “m” belongs to Language L2.
•Intersection of L1 and L2 consists of all the strings that
are present with both the languages L1 and L2.
•The Complement of L1 with respect to the alphabet ∑
consists of all the strings over ∑ that are not in L1.
CAPP C12: Introduction to Theory of Computation Slide Number 22
Basic Operations on Language …
•Let L1 and L2 are languages over common alphabet ∑, then
…
•The Kleene Star: The language consisting of all words
that are concatenations of zero or more words in the
language under consideration.
•The Kleene Closure i.e. the language consisting of all
words that are concatenations of One or more words in
the language under consideration.
CAPP C12: Introduction to Theory of Computation Slide Number 23
Basic Operations on Language …
•Let L1 and L2 are languages over common alphabet ∑, then
…
•String Homomorphism: String Homomorphism is
defined as
•ϵ free String Homomorphism :ϵ free String
Homomorphism is defined as
CAPP C12: Introduction to Theory of Computation Slide Number 24
Basic Operations on Language …
•Let L1 and L2 are languages over common alphabet ∑, then
…
•Substitution: Substitution
•Inverse Homomorphism: Inverse Homomorphism is
defined as
•Reverse: Reverse
CAPP C12: Introduction to Theory of Computation Slide Number 25
String Homomorphism
•A string homomorphism i.e. homomorphism in formal
language theory is a string substitution such that each
character is replaced by a single string i.e. f(a) = s where ‘s’
is a string, for each character a.
•String homomorphism is monoid morphism on the free
monoid that preserves the empty string and the binary
operation of string concatenation.
CAPP C12: Introduction to Theory of Computation Slide Number 26
String Homomorphism …
•For any given language L, let the set f(L) is termed as the
homomorphic image of L, the inverse homomorphic image
of a string s is defined as f-1(s)={w|f(w)=s}.
•The inverse homomorphic image of a language L is defined
as f-1(L)= {s|s∈ L}.
•In general, f(f-1(L))≠L while f(f-1(L))⊆ L and L ⊆ f(f-1(L)).
CAPP C12: Introduction to Theory of Computation Slide Number 27
Chomsky Hieraerchy of Language
•Type 0 i.e. Unrestricted Language generated by
Unrestricted Grammar accepted by Turing Machine
•Type 1 i.e. Context Sensitive Language generated by
Context Sensitive Grammar and accepted by Linear Bound
Automata
•Type 2 i.e. Context Free Language generated by Context
Free Grammar and accepted by Pushdown Automata
CAPP C12: Introduction to Theory of Computation Slide Number 28
Chomsky Hierarchy of Language
•Type 3 i.e. Regular Language accepted by Finite Automata
CAPP C12: Introduction to Theory of Computation Slide Number 29
Chomsky Hierarchy of Language
Type 0
Type 1
Type 2
Type 3
CAPP C12: Introduction to Theory of Computation Slide Number 30
Properties of String
•Properties of String
CAPP C12: Introduction to Theory of Computation Slide Number 31
Mathematical Object
•Number is the Mathematical Object used to
•Count
•Measure
•Label
•The notational symbol that represents a number is called
NUMERAL.
CAPP C12: Introduction to Theory of Computation Slide Number 32
Mathematical Induction
•Mathematical Induction is a special way of proving things.
•It has only 2 steps:
•Step 1 i.e. Basic Step: Show it is true for the first one
•Step 2 i.e. Induction Step: Show that if any one is true
then the next one is true
•Then all are true
•Also termed as “Domino Effect”.
CAPP C12: Introduction to Theory of Computation Slide Number 33
Mathematical Induction …
•If a statement S is to be proved for every positive integer
‘n’, n> n0, where n0 is some fixed integer, then this can be
done through the principle of Mathematical Induction.
CAPP C12: Introduction to Theory of Computation Slide Number 34
Mathematical Induction …
•This involves only 2 steps:
•Step 1 i.e. Basic Step: In this step, the statement ‘S’ is
proved to be true for n = n0.
•Step 2 i.e. Induction Step: In this step, S is assumed to
be true for some integer “n=k”. This statement is used
to prove that S is true for n = k+1.
CAPP C12: Introduction to Theory of Computation Slide Number 35
Mathematical Induction …
•Then all are true
•Also termed as “Domino Effect i.e. Ripple Effect”.
CAPP C12: Introduction to Theory of Computation Slide Number 36
Mathematical Induction …
•Then all are true
•Also termed as “Domino Effect i.e. Ripple Effect”.
•Considering the example “Is 3n-1 is a multiple of 2?”.
•First, we try to show that if is true for n=1.If n = 1, 3n-1
reduces to 31-1=2, which is divisible by 2. Hence 31-1 is
true.
•Now, let us assume that for n=k, 3k-1 is true.
CAPP C12: Introduction to Theory of Computation Slide Number 37
Mathematical Induction …
•Now, we try to show that “3k+1-1 is divisible by 2” is true.
3k+1-1=31X3k-1
=3X3k-1
= (2+1)X3k-1
= 2 X 3k + 1X3k-1
= Multiple of 2 + Multiple of 2 (our assumption)
= Multiple of 2 (Hence Proved)
CAPP C12: Introduction to Theory of Computation Slide Number 38
Mathematical Induction …
•Similarly, we can prove that 3k-1-1 is multiple of 2.
CAPP C12: Introduction to Theory of Computation Slide Number 39
Principle of Mathematical Induction
•Mathematical induction is a mathematical proof
technique.
•It is used to prove that if a statement P(n) holds for every
natural number n = 0, 1, 2, 3, . . . ; that is, the overall
statement is a sequence of infinitely many cases P(0), P(1),
P(2), P(3), . . . .
CAPP C12: Introduction to Theory of Computation Slide Number 40
Principle of Mathematical Induction …
•A mathematical proof is nothing but “an inferential
argument for a mathematical statement”, showing that the
stated assumptions logically ensure the conclusion.
•3k+1-1 is divisible by 2?
•K=0, P(0)= 30+1-1, P(1)= 31+1-1, P(2)= 32+1-1
CAPP C12: Introduction to Theory of Computation Slide Number 41
Principle of Mathematical Induction …
•The argument may use other previously established
statements like theorems; but every proof can, in principle,
be constructed using only certain basic or original
assumptions known as axioms, along with the accepted
rules of inference.
CAPP C12: Introduction to Theory of Computation Slide Number 42
Principle of Mathematical Induction …
•Proofs are examples of exhaustive deductive reasoning
which establish logical certainty, to be distinguished from
empirical arguments or non-exhaustive inductive
reasoning which establish “reasonable expectation”.
•Presenting many cases in which the statement holds is not
enough for a proof, which must demonstrate that the
statement is true in all possible cases.
CAPP C12: Introduction to Theory of Computation Slide Number 43
Principle of Mathematical Induction …
•An unproven proposition that is believed to be true is
known as a conjecture, or a hypothesis if frequently used
as an assumption for further mathematical work.
•Mathematical induction proves that we can climb as high
as we like on a ladder, by proving that we can climb onto
the bottom rung i.e. the basis and that from each rung we
can climb up to the next one i.e. the step.
CAPP C12: Introduction to Theory of Computation Slide Number 44
Recursive Definition
•Applying a rule or formula to the result repeatedly / again
and again / recursively.
•Recursive Definition, or Inductive Definition, is used to
define the elements in a set in terms of other elements in
the set.
CAPP C12: Introduction to Theory of Computation Slide Number 45
Recursive Definition …
•Some of the recursively definable objects are
•Factorials
•Natural Numbers N={n+1:n∈ N}
•Fibonacci Numbers
•The Cantor Ternary Set
CAPP C12: Introduction to Theory of Computation Slide Number 46
Recursive Definition …
•Look at the following “recursive definition” of “an
arithmetic expression”
•An arithmetic expression is any of the following:
•A Numeric Constant
•An Identifier (of a numeric type variable or constant)
•An Arithmetic Expression enclosed in parentheses
•Two Arithmetic Expressions separated by a Binary
Arithmetic Operator. (a = (b + c - 1))
CAPP C12: Introduction to Theory of Computation Slide Number 47
