Scribd
Upload
52 views2 pages

ToC Updated Syllabus 2023 Batch Students

The document outlines the syllabus for the Theory of Computation course under the B.E. Computer Science and Engineering program, effective from the academic year 2025-26. It includes course objectives, modules covering topics such as finite automata, regular languages, context-free grammars, pushdown automata, and Turing machines, along with course outcomes and recommended textbooks. The course aims to equip students with the ability to apply core concepts in computation theory and design various computational models.

Uploaded by

rcbforevervk1800
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
52 views2 pages

ToC Updated Syllabus 2023 Batch Students

The document outlines the syllabus for the Theory of Computation course under the B.E. Computer Science and Engineering program, effective from the academic year 2025-26. It includes course objectives, modules covering topics such as finite automata, regular languages, context-free grammars, pushdown automata, and Turing machines, along with course outcomes and recommended textbooks. The course aims to equip students with the ability to apply core concepts in computation theory and design various computational models.

Uploaded by

rcbforevervk1800
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

`

B.E. COMPUTER SCIENCE AND ENGINEERING


Choice Based Credit System (CBCS) applicable for 2022 Scheme
SEMESTER -V
Theory of Computation (3:2:0:0) 4
(Effective from the academic year 2025-26)
Course Code BCS503 CIE Marks 50
Teaching Hours/Week (L:T:P:S) 3:2:0:0 SEE Marks 50
Total Number of Contact Hours 40 (Theory) + 13 ( Tutorial ) Exam 03
Hours
Course Objectives:
This course will enable students to:
1. Apply the core concepts in Automata and Theory of Computation
2. Design Grammars for context free languages
3. Prove theorems in automata theory using suitable properties
4. Design PDA and Turing machines for suitable languages
Preamble:
In this course, we delve into the elegant theories and intricate models that define what is
computationally possible and impossible. From finite automata to Turing machines, from
regular languages to undecidability, we explore the boundaries and capabilities of
computation itself.
Module 1
Introduction to Finite Automata:
Introduction to Finite Automata; The central concepts of Automata theory; Deterministic
finite automata; Nondeterministic finite automata. Finite automata with Epsilon-
transitions.
Text book : 1.5, 2.2, 2.3, 2.5 (10 Hours)
Module 2
Regular expressions, Properties of Regular Languages: Finite Automata and Regular
Regular languages:
Proving languages not to be regular languages; Closure properties of regular languages;
Equivalence and minimization of automata.
Text Book : 3.1, 3.2, 3.3, 4.1, 4.2, 4.4 (10 Hours)
Module 3
Context-Free Grammars and Languages: Context free grammars; Writing a grammar,
Leftmost derivation, rightmost derivation, Parse Trees; Applications; Ambiguity in
grammars and Languages.
Text Book: 5.1, 5.2, 5.3, 5.4 (10 Hours)
Module 4
Properties of Context-Free Languages: Normal forms for CFGs. Pushdown Automata:
Definition of the Pushdown automata; the languages of a PDA; Equivalence of and

Text Book: 7.1, 6.1, 6.2, 6.3, 6.4 (10 Hours)


`

Module 5

Introduction to Turing Machine: Problems that Computers cannot solve; The turning
machine; Programming techniques for Turning Machines; Extensions to the basic Turning
Machines; Turing Machine and Computers.
Recap: Summary of the Course

Text Book: 8.1, 8.2, 8.3, 8.4, 8.6 (10 Hours)


Course Outcomes:
The students will be able to:
CO1: Make use of the concept of abstract machines and their power to recognize the languages.
CO2: Apply the finite state machines for modeling and solving computing problems
CO3: Design grammars, PDA, Turing machine for formal languages.
CO4: Analyze the relationship of language classes, grammar and automata.
Textbooks:
1. John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman ,Introduction to Automata
Theory, Languages and Computation, Pearson Education, 3rd Edition, 2007

References:
1. Peter Linz, An Introduction to Formal Languages and Automata, 3rd Edition,
Narosa Publishers, 1998.
2. K.L.P. Mishra, Theory of Computer Science, Automata, Languages, and
Computation, PHI Learning, 3rd Edition, 2009.
3. Elaine Rich, Automata, Computability and Complexity, 1st Edition, Pearson
Education, 2012/2013.
4. John C Martin, Introduction to Languages and Automata Theory, Tata McGraw- Hill,
3rd Edition, 2007.
Continuous Comprehensive Assessment (CCA) suggested:
1. Problem-Solving based on real world Case Studies.
2. Gate Based Questions.

You might also like