KTU 2024 Scheme · Semester 3 · Common to CS/CA/CM/CD/CN/CC
Theory of Computation (PCCST302) Syllabus
Official KTU 2024 Scheme syllabus for Theory of Computation, Semester 3, Common to CS/CA/CM/CD/CN/CC (Computer Science and Engineering).
Course Code
PCCST302
Credits
4
Teaching Hours
3:1:0:0 (L:T:P:R)
CIE Marks
40
ESE Marks
60
Exam Duration
2 Hrs 30 Min
Prerequisites
PCCST205 (Discrete Mathematics)
Semester
Semester 3
Course Objective
To introduce the concept of formal languages; to discuss the Chomsky classification of formal languages with a discussion on grammar and automata for regular, context-free, context-sensitive, and unrestricted languages; and to discuss the notions of decidability and the halting problem.
Module-wise Syllabus
Module 1
11 contact hoursFoundations: motivation for studying computability, need for mathematical modeling — automata, introducing automata through simple models (on/off switch, coffee vending machine), three basic concepts — alphabet, strings, and languages. Finite Automata: formal definition of a finite automaton, deterministic finite automata (DFA), regular languages, nondeterminism (guess and verify paradigm), formal definition of a nondeterministic finite automaton, NFA with epsilon transitions, eliminating epsilon transitions, equivalence of NFAs and DFAs — the subset construction, DFA state minimization, applications of finite automata (text search, keyword recognition).
Module 2
11 contact hoursRegular Expressions: formal definition, building regular expressions, equivalence with finite automata — converting FA to regular expressions and back, pattern matching, regular grammar and its equivalence with FA. Properties of Regular Languages: closure and decision properties (with proofs), the pumping lemma for regular languages (with formal proof) and its use to prove non-regularity of languages.
Module 3
11 contact hoursContext-Free Grammars and Applications: formal definition, designing context-free grammars, leftmost/rightmost derivations, parse trees, ambiguous grammars, inherent ambiguity, CFGs and programming languages. Pushdown Automata: formal definition, DPDA and NPDA, examples, equivalence of NPDAs and CFGs (conversions in both directions). Simplification of Context-Free Languages: eliminating useless symbols/productions, epsilon productions, unit productions, Chomsky normal form, Greibach normal form. Properties of Context-Free Languages: pumping lemma (with formal proof), closure and decision properties.
Module 4
11 contact hoursTuring Machines: formal definition, examples — Turing machines as language acceptors and as computers of functions, variants of Turing machines, recursive and recursively enumerable languages, Chomskian hierarchy, linear bounded automaton as a restricted TM. Computability: Church-Turing thesis, encoding of TMs, universal machine and diagonalization, reductions, decidable and undecidable problems, the halting problem, Post correspondence problem and the proofs for their undecidability.
Course Outcomes
- CO1Classify formal languages into regular, context-free, context-sensitive, and unrestricted languages.
- CO2Develop finite state automata, regular grammar, and regular expressions.
- CO3Model push-down automata and context-free grammar representations for context-free languages.
- CO4Construct Turing machines to accept recursive and recursively enumerable languages.
- CO5Describe the notions of decidability and undecidability of problems, including the halting problem.
Assessment Pattern (CIE: 40 marks, ESE: 60 marks)
Continuous Internal Evaluation (CIE)
| Attendance | 5 |
| Assignment / Microproject | 15 |
| Internal Examination 1 (Written) | 10 |
| Internal Examination 2 (Written) | 10 |
End Semester Examination (ESE)
Total 60 marks, 2 Hrs 30 Min. See the official KTU syllabus document for the exact Part A / Part B question pattern for this course.
Textbooks & Reference Books
Textbooks
- An Introduction to Formal Languages and Automata — Peter Linz and Susan H. Rodger (Jones and Bartlett Publishers, Inc, 7th edition, 2022)
- Introduction to Automata Theory, Languages, And Computation — John E. Hopcroft, Jeffrey D. Ullman (Rainbow Book Distributors, 3rd edition, 2015)
- Automata and Computability — Dexter C. Kozen (Springer, 1st edition, 2007)
Reference Books
- Introduction to the Theory of Computation — Michael Sipser (Cengage India Private Limited, 3rd edition, 2014)
- Introduction to Languages and the Theory of Computation — John C Martin (McGraw-Hill Education, 4th edition, 2010)
- Theory of Computation: A Problem-Solving Approach — Kavi Mahesh (Wiley, 1st edition, 2012)
- Elements of the Theory of Computation — Harry R. Lewis, Christos Papadimitriou (Pearson Education, 2nd edition, 2015)
Frequently Asked Questions
How many credits is KTU Theory of Computation (PCCST302)?
4 credits, with 3:1:0:0 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.
How many modules are in the PCCST302 syllabus?
4 modules, 44 total contact hours.
What is the CIE and ESE mark split for this course?
CIE (Continuous Internal Evaluation): 40 marks. ESE (End Semester Examination): 60 marks, 2 Hrs 30 Min. Total: 100 marks.
What are the recommended textbooks for PCCST302?
An Introduction to Formal Languages and Automata (Peter Linz and Susan H. Rodger); Introduction to Automata Theory, Languages, And Computation (John E. Hopcroft, Jeffrey D. Ullman); Automata and Computability (Dexter C. Kozen).
Is this syllabus specific to one branch, or common to others too?
This Semester 3 course is listed under Common to CS/CA/CM/CD/CN/CC at KTU under the 2024 Scheme — check the course header above for which branches it's common to.
Need help with KTU Theory of Computation?
Learnizo offers live, 1-on-1 online tuition for KTU CSE subjects — matched to your exact module and semester.
Explore BTech CSE Tuition