K S R INSTITUTE FOR ENGINEERING AND TECHNOLOGY

Form ACF - 02
An Autonomous Institution
(Approved by AICTE, New Delhi, Affiliated to Anna University & Accredited by NAAC (A+) & NBA)
K.S.R. Kalvi Nagar, Tiruchengode – 637 215,
Namakkal District, Tamil Nadu
Ph: 04288-274773, FAX: 04288-274745, Email: principal@ksriet.ac.in

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING (CYBERSECURITY)

COURSE PLAN
Academic Year,
Degree / Program B.E / CSE(CS) 2023-2024, EVEN
Semester
Course Code & Course CS3452 & THEORY OF
Year / Sem. II / IV
Title COMPUTATION
Name of the Faculty &
K.Sudha, AP&Head / CSE-CS Regulation R2021
department
E-mail hod_csecs@ksriet.ac.in Contact Number 6380118908

INTRODUCTION ABOUT THE COURSE

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.
Automata enables 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 analyze the dynamic behavior of discrete systems. Automata originated from the word
“Automaton” which is closely related to “Automation”.
Unit 1: Automatons are abstract models of machines that perform computations on an input by moving
through a series of states or configurations. At each state of the computation, a transition
function determines the next configuration on the basis of a finite portion of the present
configuration.
Unit 2: Regular Expressions are an algebraic way to describe languages. Regular Expressions describe
exactly the regular languages. If E is a regular expression, then L(E) is the regular language it
defines. For each regular expression E, we can create a DFA A such that L(E) = L(A).
Unit 3: A context free grammar (CFG) is a forma grammar which is used to generate all the possible
patterns of strings in a given formal language. It is defined as four tuples − G=(V,T,P,S) G is a
grammar, which consists of a set of production rules. CFL is a language which is generated by a
context-free grammar or Type 2 grammar (according to Chomsky classification) and gets
accepted by a Pushdown Automata.
Unit 4: Turing machine to develop a theory of undecidable problems that is problems that no computer
can solve. While a Turing machine looks nothing like a PC, and would be grossly inefficient
should some startup company decide to manufacture and sell them, the Turing machine long has
been recognized as an accurate model for what any physical computing device is capable of
doing.
 Unit 5: The problems for which we can't construct an algorithm that can answer the problem correctly in
the infinite time are termed as Undecidable Problems in the theory of computation (TOC). A
problem is undecidable if there is no Turing machine that will always halt an infinite amount of
time to answer as 'yes' or 'no'.
OBJECTIVES
 To understand foundations of computation including automata theory
 To construct models of regular expressions and languages.
 To design context free grammar and push down automata
 To understand Turing machines and their capability
 To understand Undecidability and NP class problems
APPLICATION
 Speech Recognition
 Natural Language Processing
 Regular Expression Matching
 Video Games
PREREQUISITE
 Discrete Mathematics (graphs, trees, logic and proof techniques)
 Data Structures and Recursion
 Compilers
COURSE OUTCOMES:
At the end of the course the students would be able to
Bloom’s Taxonomy
COs Course Outcome
Level
CO1 Construct automata theory using Finite Automata K5
CO2 Write regular expressions for any pattern K2
CO3 Design context free grammar and Pushdown Automata K6
CO4 Design Turing machine for computational functions K6
CO5 Differentiate between decidable and undecidable problems K2

PROGRAM OUTCOMES (POs)

PO1 Engineering Knowledge PO7 Environment and sustainability
PO2 Problem Analysis PO8 Ethics
PO3 Design/development of solutions PO9 Individual and team work
PO4 Conduct investigations of complex PO10
Communication
problems
PO5 Modern tool usage PO11 Project management and finance
PO6 The Engineer and society PO12 Life-long learning
PROGRAM SPECIFIC OUTCOMES (PSOs)
Programming Skill: Work as Software Engineers for providing solutions to real world problems using
programming languages and open source software.
Web Designing Skill: Ability to use the web designing skill to establish new solutions for the societal
needs.
COURSE OUTCOME AND PROGRAMME OUTCOMES MAPPING:
COs/
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2
POs
CO1 1 3 2 3 - - - - 1 1 2 3 1 1
CO2 2 2 3 2 1 - - - 3 3 2 3 1 1
CO3 2 2 3 2 1 - - - 1 3 1 2 1 1
CO4 2 2 2 1 - - - - 1 3 3 2 1 1
CO5 2 2 2 1 1 - - - 1 1 3 2 1 1
Avg. 2 2 2 2 1 - - - 1 2 2 2 1 1

S. Date & Teaching Duration Page

Topics to be covered Resources
(in min.)
No. Hour Aids No.
UNIT - I AUTOMATA AND REGULAR EXPRESSIONS
Need for automata theory - Introduction to formal proof – Finite Automata (FA) – Deterministic Finite Automata (DFA) –
Non-deterministic Finite Automata (NFA) – Equivalence between NFA and DFA – Finite Automata with Epsilon
transitions – Equivalence of NFA and DFA- Equivalence of NFAs with and without ε-moves- Conversion of NFA into
DFA – Minimization of DFAs
Introduction 5
Need for automata theory 15
21.02.2024
1. Activity- QA 5 CT T1 5 01-13
(2)
Introduction to formal proof 15
Summary 5
Recap 5
Finite Automata (FA) 15
22.02.2024
2. Activity – Quiz 5 CT T1 37-54
(1)
Deterministic Finite Automata (DFA) 15
Summary 5
Recap 5
Non-deterministic Finite Automata 15
27.02.2024 Flipped
3. Activity-Random Pick 5 T1 55-65
(4) Classroom
Equivalence between NFA and DFA 15
Summary 5
Recap 5
Finite Automata with ε transitions 15
28.02.2024
4 Activity – Just a minute 5 Seminar T1 72-75
(2)
Gradiance Problems 15
Summary 5
Recap 5
Equivalence of NFAs with 15
29.02.2024 ε-moves
5. CT T1 75-80
(1) Activity- Problem Solving 5
Gradiance Problems 15
Summary 5
6 04.03.2024 Recap 5 CT T1 75-80
(2) Equivalence of NFAs without 15
S. Date & Duration Teaching Page
Topics to be covered (in min.) Resources
No. Hour Aids No.
ε-moves
Activity – Random Pick 5
Gradiance Problems 15
Summary 5
Recap 5
Gradiance Problems 15
05.03.2024
7. Activity – Just a minute 5 PPT W4 -
(4)
Conversion of NFA into DFA 15
Summary 5
Introduction 5
Gradiance Problems 15
06.03.2024
8. Activity- Problem Solving 5 CT T1 160-163
(2)
Minimization of DFAs 15
Summary 5
Introduction 5
Gradiance Problems 15
07.03.2024
9. Activity – QA 5 TPS T1 167-168
(1)
Gradiance Problems 15
Summary 5
UNIT- II REGULAR EXPRESSIONS AND LANGUAGES
Regular expression – Regular Languages- Equivalence of Finite Automata and regular expressions – Proving languages to
be not regular (Pumping Lemma) – Closure properties of regular languages.
Introduction 5
Regular Expression 15
12.03.2024
10. Activity – Quiz 5 Flipped T1 7 85-87
(4)
The Operators of Regular Expressions 15 Classroom
Summary 5
Recap 5
Building Regular Expressions 15
13.03.2024
11. Activity – Random Pick 5 PPT T1 87-91
(2)
Precedence of RE Operators 15
Summary 5
Recap 5
Regular Languages 15
14.03.2024
12. Activity – Brainstorming 5 CT T1 55-59
(1)
Equivalence of FA and RE 15
Summary 5
Recap 5
Converting DFA`s to RE by Eliminating
15
18.03.2024 States
13. T1 189-195
(2) Activity – Q&A 5 CT
Contd., 15
Summary 5
14. 19.03.2024 Introduction 5 T1 102-107
(4) Converting RE to Automata 15 CT
S. Date & Duration Teaching Page
Topics to be covered (in min.) Resources
No. Hour Aids No.
Activity – Quiz 5
Contd., 15
Summary 5
Recap 5
Applications of Regular Expressions 15
20.03.2024
15. Activity – Random Pick 5 PPT/GD T1 109-114
(2)
Contd., 15
Summary 5
Recap 5
Proving languages to be not regular 15
21.03.2024 Activity – Random Pick 5
16. The Pumping Lemma for Regular CT T1 127-129
(1) 15
Languages
Summary 5
Recap 5
Applications of the Pumping Lemma 15
26.03.2024 Activity – QA 5
17. PPT T1 129-133
(4) Closure properties of regular languages 15
Summary 5
Recap 5
Closure of Regular Languages Under
15
Boolean Operations
27.03.2024
18. Activity – Problem Solving 5 Seminar T1 133-147
(2)
Reversal, Homomorphisms & Inverse
15
Homomorphisms
Summary 5
UNIT- III CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA
Types of Grammar - Chomsky‘s hierarchy of languages -Context-Free Grammar (CFG) and Languages – Derivations and
Parse trees – Ambiguity in grammars and languages – Push Down Automata (PDA): Definition – Moves - Instantaneous
descriptions -Languages of pushdown automata – Equivalence of pushdown automata and CFG-CFG to PDA-PDA to
CFG – Deterministic Pushdown Automata.
Introduction 5
Types of Grammar 15
28.03.2024
19. Activity – Random Pick 5 Flipped R3 120-122
(1)
Chomsky‘s hierarchy of languages 15 Class
Summary 5
Epitomize 5
Context-Free Grammar (CFG) and
15
01.04.2024 Languages
Activity – Quiz 5 CT T1 171-175
20. (2)
Contd., 15
Summary 5
02.04.2024 Epitomize 5 TPS T1
21. Derivations Using a Grammar 15
S. Date & Duration Teaching Page
Topics to be covered (in min.) Resources
No. Hour Aids No.
Activity – Brainstorming 5 175-181
Leftmost and Rightmost Derivations 15
(4)
Summary 5
Recap 5
Parse trees 15
03.04.2024 Activity – Quiz 5 T1 183-193
22. (2) Contd., 15 PPT
Summary 5
Epitomize 5
Ambiguity in grammars and languages 15
04.04.2024 Activity – Random pick 5
23. SS T1
(1) 207-215
Contd., 15
Summary 5
Pushdown Automata 5
Definition of the Pushdown
15
10.04.2024 Automaton 225-233
24. CT T1
(2) Activity – Just a minute 5
Moves - Instantaneous descriptions 15
Summary 5
Epitomize 5
Languages of pushdown automata 15
15.04.2024
25. Activity – Problem Solving 5 CT T1 234-247
(2)
Equivalence: CFG to PDA 15
Summary 5
Recap 5
16.04.2024 PDA to CFG 15
26. Activity – Problem Solving 5 T1 247-251
(4) CT
Contd., 15
Summary 5
Recap 5
17.04.2024 Deterministic Pushdown Automata 15
E- 252-256
27. Activity – Quiz 5 T1
(2) Learning
Contd., 15
Summary 5
UNIT IV NORMAL FORMS AND TURING MACHINES
Normal forms for CFG – Simplification of CFG- CNF and GNF – Pumping lemma for CFL – Closure properties of
Context Free Languages –Turing Machine: Basic model – definition and representation – Instantaneous Description –
Language acceptance by TM – TM as Computer of Integer functions – Programming techniques for TM (subroutines).
Introduction 5
18.04.2024 Simplification of CFG 15
28. Activity – Quiz 5 CT R3 189-201
(1)
Normal forms for CFG 15
Summary 5
29. 23.04.2024 Recap 5 T2ttt R3 201-206
Chomsky Normal Form (CNF) 15 CT
S. Date & Duration Teaching Page
Topics to be covered (in min.) Resources
No. Hour Aids No.
Activity – Random pick 5
Supplementary Examples 15
(4)
Summary 5
Recap 5
Greibach Normal Form (GNF) 15
24.04.2024 206-213
30. Activity – Problem Solving 5 R3
(2) CT
Supplementary Examples 15
Summary 5
Epitomize 5
25.04.2024 Pumping lemma for CFL 15
31. Activity – Random Pick 5 SS T1 279-286
(1)
Contd., 15
Summary 5
Epitomize 5
Closure properties of Context Free
15
29.04.2024 Languages E-
32. T1 287-297
(2) Activity – Brainstorming 5 Learning
Contd., 15
Summary 5
Epitomize 5
Turing Machine: Basic model – 15
30.04.2024 definition and representation
33 Activity – QA 5 CT R3 277-283
(4)
Representation of Turing Machines 15
Summary 5
Recap 5
Instantaneous Description 15 327-331
T1
02.05.2024 Activity – Quiz 5 &
34. PPT &
(1) Language acceptance by Turing 283-274
15 R3
Machine
Summary 5
Epitomize 5
TM as Computer of Integer functions 15
06.05.2024 Activity – Quiz 5 -
35. VP V1
(2) Contd., 15
Summary 5
Recap 5
Programming Techniques for Turing
15
07.05.2024 Machine
36. SS T1 337-343
(4) Activity – Random Pick 5
Contd., 15
Summary 5
UNIT V UNDECIDABILITY
Unsolvable Problems and Computable Functions –PCP-MPCP- Recursive and recursively enumerable languages –
S. Date & Duration Teaching Page
Topics to be covered (in min.) Resources
No. Hour Aids No.
Properties - Universal Turing machine -Tractable and Intractable problems - P and NP completeness – Kruskal’s
algorithm – Travelling Salesman Problem- 3-CNF SAT problems
Introduction 5
Unsolvable Problems 15
08.05.2024 Flipped
37. Activity – Just a minute 5 T2 331-353
(2) Classroom
Computable Functions 15
Summary 5
Epitomize 5
Post`s Correspondence Problem 15
09.05.2024 23-25
38. Activity – Quiz 5 CT R6
(1)
Contd., 15
Summary 5
Introduction 5
Modified PCP 15
14.05.2024 Activity – Mind map 5
39. CT V4 22-23
(4) Contd., 15
Summary 5
Epitomize 5
Recursive languages 15
15.05.2024 Activity – Idea line up 5
40. PPT R6 40-45
(2)
Recursively enumerable languages 15
Summary 5
Introduction 5
Properties 15 45-46
16.05.2024 Flipped
41. Activity – Mind map 5 R6 &
(1) Classroom
Universal Turing machine 15 47-51
Summary 5
Epitomize 5
Tractable & Intractable problems 15
29.05.2024
42. Activity – Quiz 5 CT R6 63-70
(2)
P and NP completeness 15
Summary 5
Epitomize 5
Kruskal’s algorithm 15
30.05.2024 E-
43. Activity – Quiz 5 R6 74-80
(1) Learning
Contd., 15
Summary 5
Epitomize 5
Travelling Salesman Problem 15
03.06.2024 431-433
44. Activity – GD 5 CT T1
(2)
Contd., 15
Summary 5
45. 04.06.2024 Epitomize 5 SS T1, W1
(4) 3-CNF SAT problems 15 447-458
 S. Date & Duration Teaching Page
Topics to be covered (in min.) Resources
No. Hour Aids No.
Activity – Random pick 5
Contd., 15
Summary 5

CONTENT BEYOND SYLLABUS

Conduction Resource Relevant Pos,

S. No. Date & Hour Topics
Mode Person Details PSOs
Quantum
1. E-Learning Mr.D.Balakrishnan
Computation
PO1,PO2,PO3,
05.06.2024 & (2) Language Classes
PSO1, PSO2
2. Based on E-Learning Mr.D.Balakrishnan
Randomization

Teaching Aids:-

* JAM- Just a minute talk, CT- Chalk & Talk, VP- Video presentation, PPT- Power point presentation, RP- Random
picking, SS- Short seminar, Q&A- Question & Answers.

TEXT BOOKS
Hopcroft J.E., Motwani R. & Ullman J.D., "Introduction to Automata Theory, Languages
1
and Computations", 3rd Edition, Pearson Education, 2008
John C Martin , "Introduction to Languages and the Theory of Computation", 4th Edition,
2
Tata McGraw Hill, 2011
REFERENCES
Harry R Lewis and Christos H Papadimitriou , "Elements of the Theory of Computation",
1
2nd Edition, Prentice Hall of India, 2015
2 Peter Linz, "An Introduction to Formal Language and Automata", 6th Edition, Jones & Bartlett, 2016
K.L.P.Mishra and N.Chandrasekaran, “Theory of Computer Science: Automata Languages
3
and Computation”, 3rd Edition, Prentice Hall of India, 2006
VIDEO LINKS
1 https://www.youtube.com/watch?v=yLGwJoeA84Q
2 https://archive.nptel.ac.in/courses/106/104/106104148/
WEB REFERENCES
1 www.gradiance.com
2 https://www.javatpoint.com/daa-3-cnf-satisfiability
3 https://cse.iitkgp.ac.in/~somindu/toc-2019/toc.html
4 https://www.geeksforgeeks.org/conversion-from-nfa-to-dfa/
ASSESMENT SYSTEM
Continuous Internal Examination End Semester Examination
L T P C
(CIA) (ESE)
3 0 0 3 Theory Only (40%) Theory Only (60%)
CONTINUOUS INTERNAL ASSESSMENT
THEORY
Assessment Portions Duration Max. Mark Max CIA Marks

CIE - 1 2.5 units 3 Hours 100

CIE - 2 2.5 units 3 Hours 100 Best 2 out of 3 and
Improvement Converted to 60
2.5 units 3 Hours 100
/ Missed Test
Quizzes (10 MCQ per unit) 20
Other
Assessment Assignment / Case Study / 40
Seminar / Tutorial / Mini Project / 20
Methods
Open Book Test
100*

*The weighted average shall be converted into 40 marks for internal assessment.
LABORATORY
Evaluation of Laboratory Record Model Practical Examination Total
(100 Marks) (100 Marks)
75 25 100*
* Total marks shall be converted into 60 marks

Course Instructor Course Coordinator Program Coordinator

Name Ms.K.Sudha Ms.K.Sudha Ms.K.Sudha

Designation AP&Head/CSE-CS AP&Head/CSE-CS AP&Head/CSE-CS

Signature

Director - Academics Principal