A. Course Handout (Version 2.

0) | Last updated on, 2022

Institute/School Name Chitkara University Institute of Engineering and Technology

Department Name Department of Computer Science & Engineering
Programme Name Bachelor of Engineering (B.E.) - Computer Science & Engineering
Course Name Theory of Computation Session 2022-2023
Course Code CS120 Semester/Batch 3rd /2022
L-T-P (Per Week) 4-0-0 Course Credits 4
Course Coordinator Name Dr. Suvarna Sharma

1. Scope and Objectives of the Course:

Upon completion of this course, students will be able to do the following:

● To understand the concept of formal languages and their relation with finite automata.
● To study and design different finite automata.
● To study context free grammars and ambiguity related issues.
● To gain familiarization with Push- Down Automata and Turing Machines.
● To explore relationship between different classes of formal languages.

2. Course Learning Outcomes:

After completion of the course, students will have demonstrated the ability to do the following:
CLO1: Gain knowledge of formal languages and classify basic operations on them.
CLO2: Illustrate Finite Automata and differentiate DFA and NFA with the help of examples
CLO3: Explain and support the properties of Regular sets using pumping lemma and theorems.
CLO4: Analyze finite automata with output and compare and contrast CFG, Regular grammar, CNF, GNF
CL05: Explain Chomsky hierarchy and be familiar with the concept of Turing Machine, Pushdown Automata
and justify with examples deterministic and non-deterministic Turing machine
CLO-PO mapping grid |Program outcomes (Pos) are available as a part of Academic Program Guide (APG)
at
Course PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
Learning
Outcomes
CLO1 H M M L M
CLO2 H M M L M
CLO3 H M H M
CLO4 H H
CLO5 H H M L M
3. Recommended Books (Reference Books/Text Books):

B01: “Introduction to Languages and Theory of Computation”, by Martin J.C., Tata McGraw- Hill Publishing
Company Limited, 3rd Edition.
B02: “Introduction to Automata Theory Languages and Computation”, Hopcroft J.E. and Ullman J.D., Narosa
Publications.
B03:” Theory of Computation, by Michel Sipser, Cengage Learning.
B04: “Introduction to Computer Theory”, Daniel I.A. Cohen, John Wiley.
4. Other readings and relevant websites:

S.No. Link of Journals, Magazines, Websites, and Research Papers

1. https://nptel.ac.in/courses/106103070
2. https://en.wikipedia.org/wiki/Finite-state_machine
3. https://www.tutorialspoint.com/automata_theory/regular_expressions.htm
4. https://www.geeksforgeeks.org/kleenes-theorem-in-toc-part-1/
5. https://www.geeksforgeeks.org/mealy-and-moore-machines-in-toc/?ref=lbp
6. https://www.geeksforgeeks.org/chomsky-hierarchy-in-theory-of-computation/?ref=lbp
7. https://www.geeksforgeeks.org/regular-expressions-regular-grammar-and-regular-languages/?ref=lbp
8.

5. Course Plan:

Lecture Topic(s)
Number
1-2 Introduction to System software including various phases / Modules in the design of a typical
compiler, Chomsky Classification.
3 Introduction to Automata: The Methods Introduction to Finite Automata, Structural Representations,
Automata and Complexity.
4-5 General Concepts of Automata Theory: Alphabets Strings, Languages, Applications of Automata
Theory.
6-7 Finite Automata: The Ground Rules, The Protocol, Deterministic Finite Automata: Definition of a
Deterministic Finite Automata.
8-9 How a DFA Processes Strings, Simpler Notations for DFA’s, Extending the Transition Function to
Strings, The Language of a DFA.
10-11 Nondeterministic Finite Automata: An Informal View. The Extended Transition Function, The
Languages of an NFA.
12-13 Equivalence of Deterministic and Nondeterministic Finite Automata.
14-15 Finite Automata With Epsilon-Transitions: Uses of ϵ -Transitions.
16-17 The Formal Notation for an ϵ -NFA, Epsilon-Closures, Extended Transitions and Languages for ϵ
-NFA’s, Eliminating ϵ - Transitions.
18-19 Regular Expressions and Languages: Regular Expressions: The Operators of regular Expressions,
Building Regular Expressions, Precedence of Regular-Expression Operators, Precedence of
Regular-Expression Operators.
20-21 Finite Automata and Regular Expressions: From DFA’s to Regular Expressions, Converting DFA’s to
Regular Expressions, Converting DFA’s to Regular Expressions by Eliminating States, Converting
Regular Expressions to Automata.
22-23 Finite Automata with output: Moore and Mealy Machines. Equivalence of Moore and
Mealy Machines.
24-25 Properties of Regular Languages: The Pumping Lemma for Regular Languages, Applications of the
Pumping Lemma Closure Properties of Regular Languages, Decision Properties of Regular Languages,
Equivalence and Minimization of Automata.
ST-1 (Lecture 1 – Lecture 20)
26-27 Context-Free Grammars and Languages: Definition of Context-Free Grammars, Derivations Using a
Grammars Leftmost and Rightmost Derivations, The Languages of a Grammar
28-29 Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, Inference Derivations, and Parse
Trees, From Inferences to Trees, From Trees to Derivations, From Derivation to Recursive Inferences,
30-31 Applications of Context-Free Grammars: Parsers, Ambiguity in Grammars and Languages: Ambiguous
Grammars, Removing Ambiguity from Grammars, Leftmost Derivations as a Way to Express
Ambiguity, Inherent Ambiguity
32-33 Pushdown Automata: Definition Formal Definition of Pushdown Automata, A Graphical Notation for
PDA’s, Instantaneous Descriptions of a PDA.
34-35 Languages of PDA: Acceptance by Final State, Acceptance by Empty Stack, From Empty Stack to Final
State, From Final State to Empty Stack
36 Equivalence of PDA’s and CFG’s: From Grammars to Pushdown Automata, From PDA’s to Grammars
37-38 Deterministic Pushdown Automata: Definition of a Deterministic PDA, Regular Languages and
Deterministic PDA’s, DPDA’s and Context-Free Languages, DPDA’s and Ambiguous Grammars
39-40 Properties of Context-Free Languages: Normal Forms for Context-Free Grammars, The Pumping
Lemma for Context-Free Languages, Closure Properties of Context-Free Languages, Decision
Properties of CFL’s
ST-2 (Lecture 20– Lecture 35)
41-42 The Turing Machine: The Instantaneous Descriptions for Turing Machines
43-44 Transition Diagrams for Turing Machines, The Language of a Turing Machine, Turing Machines and
Halting
45-46 Turing machine Examples: L= {an bn cn / n ≥ 1}, L={w c wR / w ϵ (a+b)* and c is a or b} and L = {an bn an
bn / n ≥ 1}.
47-48 Introduction: Deterministic and Non- Deterministic Turing Machines
49-50 Complexity Theory Introduction: Time and Space measures.

51-52 Complexity classes Introduction: P, NP, NPC and NP hard.

ST-3 (Lecture 36 – Lecture 52)

ETE (Lecture 1 – Lecture 52)

6. Delivery/Instructional Resources:

Lecture Topic(s) PPT Industry Web Audio-Video

Number (link of ppts Expert References
on the central Session(If yes:
server) link of ppts on
the central
server)
1-2 Introduction to System software including https://ww https://www.y
various phases / Modules in the design of w.scaler.co outube.com/w
a typical compiler, Chomsky Classification. m/topics/ph atch?v=yePqOE
ases-of-com
53AgY
piler/
3 Introduction to Automata: The Methods https://nptel. https://youtu.be
Introduction to Finite Automata, ac.in/course /S3cOulqSAm
Structural Representations, Automata and s/106/103/1 U
Complexity. 06103070/
4-5 General Concepts of Automata Theory: https://nptel. https://youtu.be
Alphabets Strings, Languages, ac.in/course /S3cOulqSAm
s/106/103/1 U
Applications of Automata Theory.
06103070/

6-7 Finite Automata: The Ground Rules, The https://nptel. https://youtu.be

Protocol, Deterministic Finite Automata: ac.in/course /S3cOulqSAm
s/106/103/1 U
Definition of a Deterministic Finite
06103070/
Automata.
8-9 How a DFA Processes Strings, Simpler https://cour https://ww
Notations for DFA’s, Extending the ses.cs.corne w.youtube.c
Transition Function to Strings, The ll.edu/cs280 om/watch?v
Language of a DFA. 0/wiki/inde =XsLjkh4EFq
x.php/Exten o
ded_transiti
on_function
10-11 Nondeterministic Finite Automata: An https://npte https://archi
Informal View. The Extended Transition l.ac.in/cours ve.nptel.ac.i
Function, The es/1061030 n/courses/1
Languages of an NFA. 70 06/104/106
104028/
12-13 Equivalence of Deterministic and https://archi
Nondeterministic Finite Automata. ve.nptel.ac.i
n/courses/1
06/104/106
104028/
14-15 Finite Automata With Epsilon-Transitions:
Uses of ϵ -Transitions.
16-17 The Formal Notation for an ϵ -NFA, https://archi
Epsilon-Closures, Extended Transitions ve.nptel.ac.i
and Languages for ϵ -NFA’s, Eliminating ϵ - n/courses/1
Transitions. 06/104/106
104028/
18-19 Regular Expressions and Languages: https://archi
Regular Expressions: The Operators of ve.nptel.ac.i
regular Expressions, Building Regular n/courses/1
Expressions, Precedence of 06/104/106
Regular-Expression Operators, 104028/
Precedence of Regular-Expression
Operators.
20-21 Finite Automata and Regular https://ww
Expressions: From DFA’s to Regular w.gatevidyal
Expressions, Converting DFA’s to Regular ay.com/dfa-
Expressions, Converting DFA’s to Regular to-regular-e
Expressions by Eliminating States, xpression-ex
Converting Regular Expressions to amples-auto
Automata. mata/
22-23 Finite Automata with output: Moore and https://ww
Mealy Machines. Equivalence of Moore w.digimat.in
and /nptel/cours
Mealy Machines. es/video/10
6105196/L3
4.html
24-25 Properties of Regular Languages: The https://archi
Pumping Lemma for Regular Languages, ve.nptel.ac.i
Applications of the Pumping Lemma n/courses/1
Closure Properties of Regular Languages, 06/104/106
Decision Properties of Regular Languages, 104028/
Equivalence and Minimization of
Automata.
26-27 Context-Free Grammars and Languages: https://ww
Definition of Context-Free Grammars, w.digimat.in
Derivations Using a Grammars Leftmost /nptel/cours
and Rightmost Derivations, The es/video/10
Languages of a Grammar 6105196/L3
6.html
28-29 Parse Trees: Constructing Parse Trees, The https://ww https://npt
Yield of a Parse Tree, Inference w.gatevidya el.ac.in/cou
Derivations, and Parse Trees, From lay.com/tag rses/10610
Inferences to Trees, From Trees to /parse-tree- 4028
Derivations, From Derivation to Recursive example-in-
Inferences, compiler-de
sign/
30-31 Applications of Context-Free Grammars: https://npt
Parsers, Ambiguity in Grammars and el.ac.in/cou
Languages: Ambiguous Grammars, rses/10610
Removing Ambiguity from Grammars, 4028
Leftmost Derivations as a Way to Express
Ambiguity, Inherent Ambiguity
32-33 Pushdown Automata: Definition Formal https://npte
Definition of Pushdown Automata, A l.ac.in/cours
Graphical Notation for PDA’s, es/1061040
Instantaneous Descriptions of a PDA. 28
34-35 Languages of PDA: Acceptance by Final https://npt
State, Acceptance by Empty Stack, From el.ac.in/cou
Empty Stack to Final State, From Final rses/10610
State to Empty Stack 4028
36 Equivalence of PDA’s and CFG’s: From https://npt
Grammars to Pushdown Automata, From el.ac.in/cou
PDA’s to Grammars rses/10610
6049
37-38 Deterministic Pushdown Automata: https://npt
Definition of a Deterministic PDA, Regular el.ac.in/cou
Languages and Deterministic PDA’s, rses/10610
DPDA’s and Context-Free Languages, 5196
DPDA’s and Ambiguous Grammars
39-40 Properties of Context-Free Languages: https://ww https://ww
Normal Forms for Context-Free w.geeksforg w.youtube.c
Grammars, The eeks.org/va om/watch?
Pumping Lemma for Context-Free rious-prope v=JDT2t6ykj
Languages, Closure Properties of rties-of-con 20
Context-Free Languages, text-free-la
Decision Properties of CFL’s nguages-cfl
/
41-42 The Turing Machine: The Instantaneous
Descriptions for Turing Machines
43-44 Transition Diagrams for Turing Machines,
The Language of a Turing Machine, Turing
Machines and Halting
45-46 Turing machine Examples: L= {an bn cn / n
≥ 1}, L={w c wR / w ϵ (a+b)* and c is a or b}
and L = {an bn an bn / n ≥ 1}.
47-48 Introduction: Deterministic and Non-
Deterministic Turing Machines
49-50 Complexity Theory Introduction: Time and
Space measures.
51-52 Complexity classes Introduction: P, NP,
NPC and NP hard.

7. Action plan for different types of learners:

Slow Learners Average Learners Fast Learners

● Remedial Classes on Saturdays ● Formative Exercises used to ● Design solutions for complex
● Encouragement for improvement using highlight concepts and notions problems
Peer Tutoring ● E-notes and E-exercises to read ● Presentation on topics beyond
● Use of Audio and Visual Materials ahead of the pedagogic those covered in CHO
● Use of Real-Life Examples material. ● Engaging students to hold hands of
slow learners by creating a Peer
Tutoring Group

8. Evaluation Scheme & Components:

Evaluation Type of Component No. of Weightage of Mode of Assessment

Component Assessments Component
Component 1 Subjective Test/Sessional Tests (STs) 03** 40% Offline

Component 2 End Term Examinations (ETE) 01 60% Offline

Total 100%
* Out of 03 STs, the ERP system automatically picks the best 02 ST marks for evaluation of the STs as final
marks.

9. Details of Evaluation Components:

Evaluation Description Syllabus Covered (%) Timeline of Examination Weightage (%)

Component
Component 01 ST 01 Up to 25% 40%

ST 02 26% - 65%

ST 03 66% - 100%
Component 02 End Term 100% 60%
Examination*
100%

* As per Academic Guidelines minimum of 75% attendance is required to become eligible for continuous
evaluation

10. Evaluation Components:

Type of Assessment Time of Total Marks Question Paper Format

Conduction 1 Mark MCQ 2 Mark MCQ 5 Mark 10 Mark
Sessional Test 1 Week 5 30 10 10 - -
Sessional Test 3 Week 11 30 10 10 - -
Sessional Test 3 Week 15 30 10 10 - -
End Term Examination 60 10 25 - -

11. Syllabus of the Course:

Course: Theory of Computation (Theory) Course Code: CS120

Lecture Topic(s) No. of Lectures Weightage %
Number
1-2 Introduction to System software including various phases / 2
Modules in the design of a typical compiler, Chomsky
Classification.
3 Introduction to Automata: The Methods Introduction to Finite 1
Automata, Structural Representations, Automata and Complexity.
4-5 General Concepts of Automata Theory: Alphabets Strings, 2
Languages, Applications of Automata Theory.
6-7 Finite Automata: The Ground Rules, The Protocol, Deterministic 2
Finite Automata: Definition of a Deterministic Finite Automata.
8-9 How a DFA Processes Strings, Simpler Notations for DFA’s, 2
Extending the Transition Function to Strings, The Language of a
DFA.
10-11 Nondeterministic Finite Automata: An Informal View. The 2
30%
Extended Transition Function, The
Languages of an NFA.
12-13 Equivalence of Deterministic and Nondeterministic Finite 2
Automata.
14-15 Finite Automata With Epsilon-Transitions: Uses of ϵ -Transitions. 2
16-17 The Formal Notation for an ϵ -NFA, Epsilon-Closures, Extended 2
Transitions and Languages for ϵ -NFA’s, Eliminating ϵ - Transitions.
18-19 Regular Expressions and Languages: Regular Expressions: The 2
Operators of regular Expressions, Building Regular Expressions,
Precedence of Regular-Expression Operators, Precedence of
Regular-Expression Operators.
20-21 Finite Automata and Regular Expressions: From DFA’s to Regular 2
Expressions, Converting DFA’s to Regular Expressions, Converting
DFA’s to Regular Expressions by Eliminating States, Converting
Regular Expressions to Automata.
22-23 Finite Automata with output: Moore and Mealy Machines. 2
Equivalence of Moore and
Mealy Machines.
24-25 Properties of Regular Languages: The Pumping Lemma for Regular 2
Languages, Applications of the Pumping Lemma Closure Properties
of Regular Languages, Decision Properties of Regular Languages,
Equivalence and Minimization of Automata.
26-27 Context-Free Grammars and Languages: Definition of 2
Context-Free Grammars, Derivations Using a Grammars Leftmost
and Rightmost Derivations, The Languages of a Grammar
28-29 Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, 2
Inference Derivations, and Parse Trees, From Inferences to Trees,
From Trees to Derivations, From Derivation to Recursive
Inferences,
30-31 Applications of Context-Free Grammars: Parsers, Ambiguity in 2
Grammars and Languages: Ambiguous Grammars, Removing
Ambiguity from Grammars, Leftmost Derivations as a Way to
Express Ambiguity, Inherent Ambiguity
32-33 Pushdown Automata: Definition Formal Definition of Pushdown 2
Automata, A Graphical Notation for PDA’s, Instantaneous
30%
Descriptions of a PDA.
34-35 Languages of PDA: Acceptance by Final State, Acceptance by 2
Empty Stack, From Empty Stack to Final State, From Final State to
Empty Stack
36 Equivalence of PDA’s and CFG’s: From Grammars to Pushdown 1
Automata, From PDA’s to Grammars
37-38 Deterministic Pushdown Automata: Definition of a Deterministic 2
PDA, Regular Languages and Deterministic PDA’s, DPDA’s and
Context-Free Languages, DPDA’s and Ambiguous Grammars
39-40 Properties of Context-Free Languages: Normal Forms for 2
Context-Free Grammars, The Pumping Lemma for Context-Free
Languages, Closure Properties of Context-Free Languages,
Decision Properties of CFL’s
41-42 The Turing Machine: The Instantaneous Descriptions for Turing 2
Machines
43-44 Transition Diagrams for Turing Machines, The Language of a Turing 2
Machine, Turing Machines and Halting
45-46 Turing machine Examples: L= {an bn cn / n ≥ 1}, L={w c wR / w ϵ 2
(a+b)* and c is a or b} and L = {an bn an bn / n ≥ 1}. 30%
47-48 Introduction: Deterministic and Non- Deterministic Turing 2
Machines
49-50 Complexity Theory Introduction: Time and Space measures. 2

51-52 Complexity classes Introduction: P, NP, NPC and NP hard. 2

This document is approved by:

Designation Name Signature

Course Coordinator Dr. Suvarna Sharma
Head Academic Delivery Dr. Srikanta K Mohapatra
Cluster Dean Prof. (Dr.) Abhineet Anand
Dean Academic Affairs Prof. (Dr.) Rajnish Sharma
Date