CS 501 Theory of Computation CCP
CS 501 Theory of Computation CCP
CS 501 Theory of Computation CCP
INDEX
Room No- C209 Number of students- 60 Class Teacher- Mr. Atish Mishra
TOC - CS V
TOC Lab CS V Sem
Monday Sem
TOC - CS
Tuesday VSem
TOC - CS VII
Thursday Sem
TOC - CS VII
Friday Sem
TOC - CS VII
Saturday Sem
B.Tech. Computer Science and Engineering
Course: CS 501 Theory of Computation
SCHEME
COURSE TITLE COURSE CREDITS– 4C THEORY
CODE PAPERS
SYLLABUS
UNIT 1
Introduction of Automata Theory: Examples of automata machines, Finite Automata as a language
acceptor and translator, Moore machines and mealy machines, composite machine, Conversion from Mealy
to Moore and vice versa.
UNIT 2
Types of Finite Automata: Non Deterministic Finite Automata (NDFA), Deterministic finite automata
machines, conversion of NDFA to DFA, minimization of automata machines, regular expression, Arden’s
theorem. Meaning of union, intersection, concatenation and closure, 2 way DFA.
UNIT 3
Grammars: Introduction to CFG, Regular Grammars, Derivation trees and Ambiguity, Simplification of
Context free grammars, Normal Forms (Chomsky Normal Form and Greibach Normal Forms).
UNIT 4
Pushdown Automata: Definition of PDA, Deterministic Pushdown Automata, PDA corresponding to given
CFG, CFG corresponding to a given PDA.
Context Free Languages: The pumping lemma for CFL’s, Closure properties of CFL’s, Decision problems
involving CFL’s.
UNIT 5
Turing Machines: Introduction, TM model, representation and languages acceptability of TM Design of TM,
Universal TM & Other modification, Church’s hypothesis, composite & iterated TM. Turing machine as
enumerators.Properties of recursive & recursively enumerable languages, Universal Turing machine
COURSE OUTCOME
CO PO MATRIX
CO & PO Mapping
CO/PO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 3 1
CO2 2 3 1
CO3 2 3 3 1
CO4 3 2 1
CO5 3 2 2
CO6 2 3 3
Note: Now map your Cos with POs and fill the given matrix: Fill 1,2 or 3 in the cell depending on 1:poor, 2: medium
and 3:strong fulfillment of CO for particular PO
ASSESSMENT MATRIX
Application/Field Trip)
Research assignments
Learning Outcome ID
Practical Experiment
Learning
Group Discussions
Presentation
Writen Test
Role Play
Seminar
Sr. No
Tutorial
Project
Module/Unit
LO1
√ √
L02
√ √
L03
Introduction of √ √
1 Automata Theory L04
√ √ √
LO5
√ √ √ √
L06
Types of Finite √
2 Automata L07
√ √ √
L08
√ √
L09
√ √
Grammar L10
3 √
L11
√ √ √
L12
√ √
L13
√ √
L14
Push Down
Automata
√ √
4 L15
√
L16
√ √
L17
√ √
L18
Turing Machine
√ √
5 L19
√ √
L20
√ √ √
EVALUATION SYSTEM
TARGET SET:
65% students score 60% or more marks upon final evaluation.
Course Curriculum Pack
This course is aimed at imparting knowledge to candidates for the Theory of Computation and aims at
building the following key competencies amongst the Students
Instructional
Sr. No Module/Units Key Learning Outcomes
Objectives
4 Definition of PDA
Pushdown Automata:
Deterministic Pushdown Automata
Chapter 6
Theory Duration (hh.mm): PDA corresponding to given CFG T1
(7:00)
CFG corresponding to a given PDA
Chapter 7
Practical Duration The pumping lemma for CFL’s
T2
(hh.mm): (6:00) Closure properties of CFL’s
Decision problems involving CFL’s
5 TM model, representation and languages
acceptability of TM
Turing Machines Design of TM
Universal TM & Other modification Chapter 8,9
Theory Duration (hh.mm): T1
Church’s hypothesis, composite & iterated
(7:00)
TM Chapter 9
Practical Duration Turing machine as enumerators T2
(hh.mm): (4:00)
Properties of recursive & recursively
enumerable languages.
Universal Turing machine
Lecture Plan To Cover/Complete The Syllabus
Reference Planned
S.No. Unit Topic Name
Books Lectures
Chapter 4
6 composite machine 1
T1
7 Numerical Solving 2
15 Chapter 6 T2 1
Introduction to CFG
III
17 Simplification of Context free grammars Chapter 6 T2 1
26 Chapter 7 T2 1
Context Free Languages: The pumping lemma for CFL’s.
Module wise List of Activities/ Experiments/Practical/Tutorials
Equipment
Sr. No Module/Units Description required
Code
1. Design a Program for creating machine that accepts
three consecutive one.
2. Design a Program for creating machine that accepts the
string always ending with 101.
3. Design a Program for Mode 3 Machine
4. Design a program for accepting decimal number
Introduction of divisible by 2. S1
1
Automata Theory 5. Design a program for creating a machine which accepts S2
string having equal no. of 1’s and 0’s.
Types of Finite
2 8. Design a Program to convert NDFA to DFA.
Automata
S1
3 Grammars:
S2
9. Design a Program to create PDA machine that accept the well-
Text(T)
Sr. No Title of the Book Author Edition / volume
Reference (R)
Equipment
Sr. No Module/Units Description of Equipment
Code
Introduction of Automata C/C++ S1
1
Theory JFLAP Simulator S2
C/C++ S1
2 Types of Finite Automata
JFLAP Simulator S2
3 Grammars:
C/C++ S1
4 Pushdown Automata:
JFLAP Simulator S2
5 Turing Machines JFLAP Simulator S2
Assessment Matrix
Application/Field Trip)
Research assignments
Learning Outcome ID
Practical Experiment
Learning
Group Discussions
Presentation
Writen Test
Role Play
Seminar
Sr. No
Tutorial
Project
Module/Unit
LO1
√ √
L02
√ √
L03
Introduction of √ √
1 Automata Theory L04
√ √ √
LO5
√ √ √ √
L06
Types of Finite √
2 Automata L07
√ √ √
L08
√ √
L09
√ √
Grammar L10
3 √
L11
√ √ √
L12
√ √
L13
√ √
L14
Push Down
Automata
√ √
4 L15
√
L16
√ √
L17
√ √
L18
Turing Machine
√ √
5 L19
√ √
L20
√ √ √
Evaluation System
Atainment Criteria:
65% students score 60% or more marks upon final evaluation.
CO & PO Mapping
CO/PO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 3 1
CO2 2 3 1
CO3 2 3 3 1
CO4 3 2 1
CO5 3 2 2
CO6 2 3 3
Note: Now map your Cos with POs and fill the given matrix: Fill 1,2 or 3 in the cell depending on 1:poor, 2: medium
and 3:strong fulfillment of CO for particular PO
Program Outcomes
Engineering Knowledge: Apply knowledge of mathematics and science, with fundamentals of Computer
PO1
Science & Engineering to be able to solve complex engineering problems related to CSE.
Problem Analysis: Identify, Formulate, review research literature and analyze complex engineering problems
PO2 related to CSE and reaching substantiated conclusions using first principles of mathematics, natural sciences
and engineering sciences
Design/Development of solutions: Design solutions for complex engineering problems related to CSE and
PO3 design system components or processes that meet the specified needs with appropriate consideration for the
public health and safety and the cultural societal and environmental considerations
Conduct Investigations of Complex problems: Use research–based knowledge and research methods
PO4 including design of experiments, analysis and interpretation of data, and synthesis of the information to
provide valid conclusions.
Modern Tool Usage: Create, Select and apply appropriate techniques, resources and modern engineering and
PO5 IT tools including prediction and modeling to computer science related complex engineering activities with an
understanding of the limitations
The Engineer and Society: Apply Reasoning informed by the contextual knowledge to assess societal,
PO6 health, safety, legal and cultural issues and the consequent responsibilities relevant to the CSE professional
engineering practice
Environment and Sustainability: Understand the impact of the CSE professional engineering solutions in
PO7
societal and environmental contexts and demonstrate the knowledge of, and need for sustainable development
Ethics: Apply Ethical Principles and commit to professional ethics and responsibilities and norms of the
PO8
engineering practice
Individual and Team Work: Function effectively as an individual and as a member or leader in diverse
PO9
teams and in multidisciplinary Settings
Project Management and Finance: Demonstrate knowledge and understanding of the engineering
PO11 management principles and apply these to one’s own work, as a member and leader in a team, to manage
projects and in multi disciplinary environments
Life-Long Learning: Recognize the need for and have the preparation and ability to engage in independent
PO12
and life-long learning the broadest context of technological change
Assignments
Assignment-1
(2) Make a FSM for calendar. (Transitions for leap year are also required).
(3) Give English description of the language of the following regular expression
0 1
q q qq3
0 1 3
1 1
qq3
1 q
4
2
(1) - Convert the following CFG into CNF, and do the LMD for “aaabaaabab”. Also draw the parse tree.
A aAb
A bAa
A bA
A aA
A €
(3) Prove that the following set is not regular using Pumping Lemma
{anbncmdmІn,m>=0}
(4) What do you understand by ambiguity? Give example and prove that the grammar is ambiguous.
Assignment-4
(1) Design a Turing Machine for the following language (with n,m,k>=0)
(2) Design a Multi Tape Turing Machine for multiplication of two variables.