BCS503 Theory Of Computation
Course Learning Objectives
● Introduce core concepts in Automata and Theory of Computation.
● Identify different Formal Language Classes and their Relationships.
● Learn concepts of Grammars and Recognizers for different formal languages.
● Prove or disprove theorems in automata theory using their properties.
● Determine the decidability and intractability of Computational problems.
SYLLABUS COPY
MODULE - 1
Introduction to Finite Automata
Structural Representations, Automata and Complexity. The Central Concepts of Automata Theory. Deterministic Finite Automata, Nondeterministic Finite Automata, An Application: Text Search, Finite Automata with Epsilon-Transitions
MODULE - 2
Regular Expressions
Finite Automata and Regular Expressions, Proving Languages not to be Regular. Closure Properties of Regular Languages, Equivalence and Minimization of Automata, Applications of Regular Expressions
MODULE - 3
Context-Free Grammars, Parse Trees, Ambiguity in Grammars and Languages, Ambiguity in Grammars and Languages, Definition of the Pushdown Automaton, The Languages of a PDA, Equivalence of PDA’s and CFG’s, Deterministic Pushdown Automata.
MODULE - 4
Normal Forms for Context-Free Grammars, The Pumping Lemma for Context-Free Languages, Closure Properties of Context-Free Languages
MODULE - 5
Introduction to Turing Machines
Problems That Computers Cannot Solve, The Turing Machine, Programming Techniques for Turing Machines, Extensions to the Basic Turing Machine, Undecidability: A Language That Is Not Recursively Enumerable
Course outcome
1. Apply the fundamentals of automata theory to write DFA, NFA, Epsilon-NFA and conversion between them.
2. Prove the properties of regular languages using regular expressions.
3. Design context-free grammars (CFGs) and pushdown automata (PDAs) for formal languages.
4. Design Turing machines to solve the computational problems.
5. Explain the concepts of decidability and undecidability.
Suggested Learning Resources
Books
1. John E Hopcroft, Rajeev Motwani, Jeffrey D. Ullman,” Introduction to Automata Theory, Languages and Computation”, Second Edition, Pearson.
Reference
1. Elain Rich, “Automata,Computability and complexity”, 1st Edition, Pearson Education,2018.
2. K.L.P Mishra, N Chandrashekaran , 3rd Edition , ‘Theory of Computer Science”,PHI,2012.
3. Peter Linz, “An introduction to Formal Languages and Automata “, 3rd Edition, Narosa Publishers,1998.
4. Michael Sipser : Introduction to the Theory of Computation, 3rd edition, Cengage learning,2013.
5. John C Martin, Introduction to Languages and The Theory of Computation, 3rd Edition, Tata McGraw –Hill Publishing Company Limited, 2013.