Introduction to Theory of Computation
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 16

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

What is TOC?
The TOC is that knowledge of computer science, which does not change
with time & technology. The course is divided into:
1
Theory of automata: Every process (including computing) can be
divided into discrete sequence of states, where there is always start state,
and there is a final state, with in between states. In this category, we may
consider the computation, and growth of life, and even the planatary
motions. All these systems are automata. The concept of automata was
given by Von Neumann, in 1940s, in the form of cellular automata.
2

Theory of languages: Under this comes all types of grammars computers’ languages grammars, spoken languages grammars, and yet
unknown grammars, and all corresponding languages. The concept of
generative grammar was given first time by Prof. Noam Chomsky, in 1956.

3

Theory of Computation: The contributors were Kurt Gödel, Alonzo
Church, Alan Turing, Kleene. However, the maximum contribution is due
to Alan Turing, who gave the concept of Turing machine in his 1936
paper (much before the computers came into existence).

kr chowdhary

TOC

2/ 16

What is TOC?
TOC attempts to establish a theory to all subjects of CS, just like
classical dynamics to motion of objects
Solvability of a problem ⇒ existence of algorithm.
TOC says that some problems are unsolvable, e.g., Russell’s
Paradox, given by {x|x ∈
/ x}
TOC deals with Physical limits of computing, Methodologies of
Algorithm design, etc.
CS is : Science of algorithm processing, representation, storage,
transmission of information
Nature of problems we deal with are classified based on their level of
difficulty for computer,i.e., complexity
Application of computer theory: writing programs to construct
compilers, assemblers, OS, ..., and languages

kr chowdhary

TOC

3/ 16

Meta-Theory and Proofs

Meta Theory: Theory about the theory (mathematics)
- Defines what is computable: A thing is computable if it can be
representable by an algorithm.
- Defines the Limits of computation
Proofs: Establishing that a statement is valid. One approach is: a
statement is valid if there is no counter example. e.g., All even
integers are divisible by 2 is valid. Proof by contradiction: find at
least a single case, where this is not true. Other approaches are:
1

2

Proofs by Deduction: Taking one value, then iterating is proof by
induction.
Proof by Induction: Execution of a sequence of program statements
is deductive proof

kr chowdhary

TOC

4/ 16

Functions
f :D →R
for a, b ∈ D, f (a) = f (b) ⇒ a = b; f is injection or one-to-one
mapping.
for each b ∈ R, there is always a ∈ D such that f (a) = b; f is
surjection (onto)
A relation which is both injection and surjection is called bijection.
Defining Natural Numbers
0 = {} = φ
0+ = 1 = {elements of 0, set 0 as element}={φ }
1+ = 2 = {φ , {φ }}
2+ = 3 = . . .
...

kr chowdhary

TOC

5/ 16

Infinite sets
Hence,
i)0 ∈ N
ii)if n ∈ N, ∴ n+ ∈ N
If there is a bijection between any set A and set n ∈ N,then A is
finite, alternatively,
If there is a bijection between any set A and set N, then A is infinite,
You can add any thing into an infinite, it results infinite only.
Example: Hilbert’s Hotel: To accommodate more guests in this
hotel, (say 1), push occupant of room 1 into 2, of 2 into room 3,
and so on. The room 1 is vacated, and ready for new guest.
You can subtract any thing from infinity, it remains infinity. For
example, you can map 40 onwards to infinity. For example,
40 ↔ 1, 41 ↔ 2, 43 ↔ 3, . . .

kr chowdhary

TOC

6/ 16

Diagonalization Theorem
Theorem
There is no bijection between infinite sets N and R.
Proof.
Assume that f : N → R is bijection, ∴,
N
R
0
0.b00 b01 b02 . . .
1
0.b10 b11 b12 . . .
2
0.b20 b21 b22 . . .
... ...
i
0.bi 0 bi 1 bi 2 . . .
Therefore this list of R is exhaustive. bij ∈ {0, 1}
Now consider the number, x = 0.¬b00 ¬b11 ¬b22 . . . Ṡince x is new,
hence the list of R is not exhaustive, this contradicts the assumption.
Thus, the mapping is not bijection. R is uncountably infinite.

kr chowdhary

TOC

7/ 16

Cantor’s Theorem
Theorem
For f : A → ℘(A), f is not surjection.
Proof.
Assume that f is surjection. Since ℘(A) are all subsets of A,
consider B ⊆ A, as an image of an element of A, which does not
include the element itself. ∴ B = {x ∈ A|x ∈
/ f (x)}
Thus, for every x ∈ A, we have x ∈ B iff x ∈
/ f (x). ∴ B ̸= f (x) for
all x ∈ A.
Thus, B is not in the image of f . This contracts our assumption
that we considered in the beginning of this proof. Hence, this proves
that f is not a surjection, and hence not a bijection also.

kr chowdhary

TOC

8/ 16

Cantor’s Theorem for infinite sets
Theorem
For f : N → ℘(N), f is not surjection.
Proof.
Assume that f is surjection, to ultimately contradict it. Consider
now:
N
⇔ ℘(N)
0
⇔ {5}
1
⇔ {2,3}
2
⇔ {1,2,5}
3
⇔ {2,4,8}
... ⇔ ...
We call the mapping between 2 and {1,2,5} as selfish, and between
1 and {2,3} as nonselfish.
Next we build a special set D of nonselfish numbers, to arrive at
contradiction. Naturally, D ∈ ℘(N). And, D = {d|d ∈ N, d ∈
/ f (d)}.
∴ D ̸= f (d) (i.e., D is not any image!).This is contradiction. This
shows that f is not surjection. (Note: Compare this with previous).
kr chowdhary

TOC

9/ 16

Functions

f :D →R
+ : int × int → int
⊆: S1 × S2 → {T , F }
Total Function: defined over the entire domain
f : x → 2x, x ∈ N, N = {0, 1, 2, . . . }
Partial Function: defined over some domain points only.
f : x → 2/x, x ∈ N
A partial function can be used to model an iteration or infinite loops.
f (x) : if (x==0) then 1 else f(x)

kr chowdhary

TOC

10/ 16

Strings and Algebraic Systems
a, b, c, d, ... for individual alphabets
x, y , z, w , ... for variable names for strings
We use symbol Σ for alphabet set for languages, e.g. Σ = {a, b}.
Set of all strings on the alphabet set Σ are represented by Σ∗
(Kleene Star).
Strings have only one operation:Concatenation. E.g., x ◦ y ,
ε ◦x = x ◦ε = x
Semigraoups are algebraic systems which are closed on some binary
operation, and have the property of associativity. For example,
⟨S, ∗⟩, such that for a, b ∈ S, there is a ∗ b ∈ S.
The semigroup is an algebra. It can be helpful in mapping all the
string operations in computer to this algebra so that they can be
formally treated, without technology boundaries of computers.
Monoid is semigroup with a neutral element. E.g., ⟨M, ⊗, 1⟩ is a
Monoid with multiplication operation.

kr chowdhary

TOC

11/ 16

Languages
Language: A Set of words (or strings) defined over some alphabet.
These words are simpler form of sentences. For example,
{aab, bba, abbbb, ε, baaa}, {ε, a, bbbb, aaa}, φ are the languages over
the alphabet set Σ = {a, b}.
{0, 1, 00, 01, 10, 11, 000, 001, . . . } is an infinite language over
Σ = {0, 1}, which contains all the binary words.
L1 = {w ∈ Σ∗ |w has property P}
L2 = {}; language with no sentences
Lε = {ε}; language with single null sentence
Let Σ = {a, b}, then Σ∗ = {ε, a, b, aa, ab, ba, bb, aaa, . . . } (Kleene
star on Σ)
L3 = {a, ab, ba, aaa} is finite language
L4 = {ap | p is prime}, L5 = {ai b i |i ∈ N}
L3 , L4 , L5 ⊆ Σ∗ .
L6 = {ai b i c i |i ∈ N}
kr chowdhary

TOC

12/ 16

Representation of Languages

Strings over Σ∗ are countably infinite. Say N
∗
Languages over Σ∗ are 2|Σ | , which is uncountably infinite, say N.
Think of the mapping, f : N → N. It is not bijection, as N > N. ∴,
some languages cannot be represented ! (what ever tools, and
methods may be used. Also, it cannot be possible to design
machines to recognize some languages, what ever may be
advancement of technology or science!) (Every algorithm is member
of N)
Algorithmic problems:
1

2

A : Σ∗1 → Σ∗2 ; A is an algorithm which maps input strings to output,
in some complex manner.
if ∀x A(x) = B(x), ∴ A ≡ B, i.e., if two algorithms A and B produce
same output for same input, then they are equal.

kr chowdhary

TOC

13/ 16

Operations on Languages

Let L1 , L2 be languages over the same alphabet Σ, then there are
following operations on L1 , L2 :
L1 ∪ L2 = {w |w ∈ L1 or w ∈ L2 }
L1 ◦ L2 = {w = xy |x ∈ L1 , y ∈ L2 }
L1 = {w ∈ Σ∗ |w ∈
/ L1 }
Lk1 = (L1 ◦ L1 ) . . . L1 , k-times, with L01 = {ε}
|
{z
}
L∗1 = {w ∈ Σ∗ |∃k ≥ 0, w ∈ Lk1 }. This is called Kleene Star of
language L1 .
∗
k
L+
1 = {w ∈ Σ |∃k ≥ 1, w ∈ L1 }.

kr chowdhary

TOC

14/ 16

Conclusion

By study of theory of computation, we reach to important
conclusions in computation, like from thermodynamic we conclude
that perpetual machines cannot be made
The course gives treatment to the subject, independent of
technology.
What problems we can solve by computers?
1
2

3

Those, that produce a definite output: e.g., sorting the numbers
Those that produce Y/N : Called Membership Problem, e.g., Is
x ∈ A?
Other, e.g., given a C program, to determine whether it will halt on
so and so given input? (Halting Problem) - unsolvable.

kr chowdhary

TOC

15/ 16

Bibliography

Chowdhary, K.R. (2025). Mathematical Preliminaries. In: Theory of
Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_1

kr chowdhary

TOC

16/ 16

