|
Objectives:
To provide the comprehensive insight into theory of computation by understanding grammar,
languages and other elements of modern language design. Also to develop capabilities to design
and develop formulations for computing models and identify its applications in diverse areas.
Expected Learning Outcomes:
1. Understand Grammar and Languages
2. Learn about Automata theory and its application in Language Design
3. Learn about Turing Machines and Pushdown Automata
4. Understand Linear Bound Automata and its applications
Unit I
Automata Theory: Defining Automaton, Finite Automaton, Transitios and Its
properties, Acceptability by Finite Automaton, Nondeterministic Finite State
Machines, DFA and NDFA equivalence, Mealy and Moore Machines,
Minimizing Automata.
Formal Languges: Defining Grammar, Derivations, Languges generated by
Grammar, Comsky Classification of Grammar and Languages, Recursive
Enumerable Sets, Operations on Languages, Languages and Automata
15L
Unit II
Regular Sets and Regular Grammar: Regular Grammar, Regular Expressions,
Finite automata and Regular Expressions, Pumping Lemma and its Applications,
Closure Properties, Regular Sets and Regular Grammar
Context Free Languages: Context-free Languages, Derivation Tree, Ambiguity
of Grammar, CFG simplification, Normal Forms, Pumping Lemma for CFG
Pushdown Automata: Definitions, Acceptance by PDA, PDA and CFG
15L
Unit III
Linear Bound Automata: The Linear Bound Automata Model, Linear Bound
Automata and Languages.
Turing Machines: Turing Machine Definition, Representations, Acceptability
by Turing Machines, Designing and Description of Turing Machines, Turing
Machine Construction, Variants of Turing Machine,
Undecidability: The Church-Turing thesis, Universal Turing Machine, Halting
Problem, Introduction to Unsolvable Problems
15L
Tutorials :
1. Problems on generating languages for given simple grammar
2. Problems on DFA and NDFA equivalence
3. Problems on generating Regular Expressions
4. Problems on drawing transition state diagrams for Regular Expressions
5. Problems on Regular Sets and Regular Grammar
6. Problems on Ambiguity of Grammar
7. Problems on working with PDA
8. Problems on working with Turing Machines
9. Problems on generating derivation trees
10. Problems on Linear Bound Automata/Universal Turing Machine
Textbook(s):
1) Theory of Computer Science, K. L. P Mishra, Chandrasekharan, PHI,3rd Edition
2) Introduction to Computer Theory, Daniel Cohen, Wiley,2nd Edition
3) Introductory Theory of Computer Science, E.V. Krishnamurthy,Affiliated East-West Press.
Additional Reference(s):
1) Theory of Computation, Kavi Mahesh, Wiley India
2) Elements of The Theory of Computation, Lewis, Papadimitriou, PHI
3) Introduction to Languages and the Theory of Computation, John E Martin, McGraw-Hill
Education
4) Introduction to Theory of Computation, Michel Sipser, Thomson