Course instructor: Prof. Preet Kanwal
Syllabus and Class Notes
| Unit | Syllabus | Vibha’s Notes |
|---|---|---|
| Unit 1 | - Mathematical Preliminaries - Basic Notations - Deterministic Finite Acceptors (DFA) - Non-Deterministic Finite Acceptors (NFA) - \(\lambda\)-NFA (Lambda-NFA) - Equivalence of Deterministic and Non-deterministic Finite Acceptors - Reduction of the number of states in Finite Automata (Minimization of DFA) |
AFLL Unit 1.pdf |
| Unit 2 | - Regular Expressions - Connection between Regular Expressions Regular Languages - Regular Grammars - Properties of Regular Languages - Pumping Lemma and identifying Non–Regular Languages |
AFLL Unit 2.pdf |
| Unit 3 | - Context Free Grammars - Parsing and Ambiguity - Formal Definitions of Pushdown Automata - Deterministic Pushdown Automata - Non Deterministic Pushdown Automata - Methods for Transforming Grammars - Two important Normal Forms - A Membership Algorithm for Context–Free Languages - Pushdown down Automata and Context Free Languages |
AFLL Unit 3.pdf |
| Unit 4 | - Properties of Context–Free Languages - Pumping Lemma for Context–Free Languages - The Standard Turing Machine - Combining Turing Machine for Complicated Tasks - Turing Thesis - Recursive and Recursively Enumerable Languages - Context Sensitive Grammar and Languages - The Chomsky Hierarchy - Some Problems that Cannot be solved by Turing Machine - PCP - Undecidable Problems for Recursively Enumerable Languages |
AFLL Unit 4.pdf |
| Unit 5 | - Propositional Logic: A very simple logic - Syntax - Semantics - A simple knowledge Base - A simple Inference procedure - Inferences and Proofs - Proof by resolution - First Order Logic: Syntax and Semantics of First order logic - Numbers, Sets and Lists - Example - The electronic circuit Domain |
AFLL Unit 5.pdf |
Textbooks:
- T1: “An Introduction to Formal Languages and Automata”, Peter Linz, Jones and Bartlett, New Delhi, India, 5th Edition, 2011
- T2: “Artificial Intelligence – A Modern Approach”, Stuart Russell and Peter Norvig, Pearson, 3rd Edition (Paperback), 2016
Reference Books:
- R1: “Theory of Computation”, Michael Sipser, Cengage Learning, New Delhi, India, 2008
- R2: “Introduction to Automata Theory, Languages, and Computation”, John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, Pearson Education, New Delhi, India, 3rd Edition, 2009
- R3: “Theory of Computation: A Problem–Solving Approach”, Kavi Mahesh, Wiley India, New Delhi, 2012