UNIVERSITY OF MADRAS
M.Sc. DEGREE PROGRAMME IN COMPUTER SCIENCE
SYLLABUS WITH EFFECT FROM 2023-2024
Title of the Paper Theory of Computation
Core–XI - Theory II Year & III Semester Credit: 3 536C3C
Objectives:
To give an overview of the theoretical foundations of computer science from the
perspective of formal languages
To illustrate finite state machines to solve problems in computing
To explain the hierarchy of problems arising in the computer
sciences.
To familiarize Regular grammars, context frees grammar.
To use basic concepts of formal languages of finite automata
techniques
Outcomes:
1. Use the concepts and techniques of discrete mathematics for theoretical K1
computer science
2. Design Finite Automata for different Regular Expressions and Languages K2
3. Identify and use different formal languages and their relationship. K3,K4
4. To solve various problems of applying normal form techniques, push down K4,K5
automata and Turing Machines
5. Analyze various concepts of undecidability and Computable Function and K6
Discuss analytically and intuitively for problem-solving situation
K1-Remember;K2-Understand;K3-Apply;K4-Analyze;K5-Evaluate; K6-Create
Unit I: Review of Mathematical Theory
Combinatorics: Review of Permutation and Combination - Mathematical Induction - Pigeon hole
principle - Principle of Inclusion and Exclusion - generating function - Recurrence relations.
Statements – Connectives – Truth Tables – Normal forms – Predicate calculus – Inference –
Theory for Statement Calculus and Predicate Calculus
Unit-II: Regular Languages and Finite Automata
Regular Expressions, Regular Languages, Application of Finite Automata, Automata with output
- Moore machine & Mealy machine, Finite Automata, Memory requirement in a recognizer,
Definitions, union- intersection and complement of regular languages, Non Deterministic Finite
Automata, Conversion from NFA to FA, ??- Non Deterministic Finite Automata, Conversion of
NFA- ? to NFA, Kleene’s Theorem, Minimization of Finite automata, Regular And Non Regular
Languages – pumping lemma.
Unit-III: Context free grammar (CFG)
Definitions and Examples, Unions Concatenations And Kleene’s of Context free language,
Regular Grammar for Regular Language, Derivations and Ambiguity , Unambiguous CFG and
Algebraic Expressions, Backus Naur Form (BNF), Normal Form – CNF.
Print to PDF with PDF Writer for Windows 8. This is a free evaluation copy. Buy full version now.
UNIVERSITY OF MADRAS
M.Sc. DEGREE PROGRAMME IN COMPUTER SCIENCE
SYLLABUS WITH EFFECT FROM 2023-2024
Unit-IV: Pushdown Automata, CFL And NCFL
Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion, Pumping lemma
for CFL, Intersections and Complements of CFL, Non-CFL.
Unit-V: Turing Machine (TM)
TM Definition, Model Of Computation, Turing Machine as Language Acceptor, TM that
Compute Partial Function, Church Turing Thesis, Combining TM, Variations Of TM, Non
Deterministic TM, Universal TM, Recursively and Enumerable Languages, Context sensitive
languages and Chomsky hierarchy.
Recommended Texts:
1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; Introduction to Automata Theory
Languages andComputation; Pearson Education, India; 3rd edition;2008
2. KENNETH H. ROSEN ; Discrete Mathematics and Its Applications (SIE) 8th Edition ;2021
Reference Books:
1. K. L. P Mishra, N. Chandrashekaran (2003), Theory of Computer Science Automata Languages
and Computation, 2nd edition, Prentice Hall of India, India.
Web References:
1. https://www.youtube.com/playlist?list=PLbtzT1TYeoMjNOGEiaRmm_vMIwUAidnQz
2. https://nptel.ac.in/courses/106106049
Mapping with Programme Outcomes:
PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO 10
CO 1 S M M S M L S S L M
CO 2 S M S L S L M L M S
CO 3 M S L M M S L S L S
CO 4 L S S L S M S L S M
CO 5 S L M S L L M S M S
S-Strong M-Medium L-Low
Print to PDF with PDF Writer for Windows 8. This is a free evaluation copy. Buy full version now.
