| Course Name | Theory of Computation |
| Course Code | 23CSE303 |
| Program | B. Tech. in Computer Science and Engineering (CSE) |
| Semester | 5 |
| Credits | 4 |
| Campus | Amritapuri ,Coimbatore,Bengaluru, Amaravati, Chennai |
Finite State machines –Deterministic finite state machine – Non-Deterministic finite state machine- Equivalence of NFA and DFA –Minimization of Finite State Machine – Regular Expression – Regular Language – Properties of Regular Languages. Designing Finite automata for real world problems.
Context Free Grammar – Derivations and Parse Tree – Pushdown Automata – Variants of Pushdown automata – Equivalence between PDA and CFG – Context Free Languages – Properties of CFL – Normal Forms. Designing push down automata for real world problems.
Context Sensitive Language- Linear Bound Automata- Turing Machine – Variants of Turing Machine – Decidability- Post correspondence problem – Introduction to undecidabl problems. Case study on formalizing real world decidable and undecidable problems.
Course Objectives
Course Outcomes
CO1: Analyse the properties of regular languages and construct finite state machines.
CO2:Understand the properties of context free languages and construct push down automata.
CO3: Understand the decidability of a problem and construct Turing machines for decidable problems.
CO4: Apply formal languages and automata for a real-world scenario.
CO-PO Mapping
| PO/PSO | PO1 | PO2 | PO3 | PO4 | PO5 | PO6 | PO7 | PO8 | PO9 | PO10 | PO11 | PO12 | PSO1 | PSO2 |
| CO | ||||||||||||||
| CO1 | 3 | 3 | 2 | 2 | – | – | – | – | – | 3 | 1 | |||
| CO2 | 3 | 3 | 2 | 2 | – | – | – | – | – | 3 | 1 | |||
| CO3 | 3 | 3 | 2 | 2 | – | – | – | – | – | 3 | 1 | |||
| CO4 | 3 | 3 | 2 | 2 | 3 | – | – | 2 | 2 | 2 | – | – | 3 | 1 |
Evaluation Pattern: 50:50
| Assessment | Internal | External |
| Midterm | 20 | |
| *Continuous Assessment (CA) | 30 | |
| End Semester | 50 |
*CA – Can be Quizzes, Assignment, Projects, and Reports
Text Book(s)
Linz P, Susan H. Rodger. An introduction to formal languages and automata. Seventh edition, Jones and Bartlett Publishers; 2022.
Reference(s)
Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages and Computation. Third Edition, Pearson; 2014.
Sipser M. Introduction to the Theory of Computation. Third Edition Cengage Publishers; 2012.
Martin JC. Introduction to Languages and the Theory of Computation. Fourth Edition McGraw-Hill; 2010.
DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.
