This course introduces formal models of computation, namely, finite automaton, pushdown automaton, and Turing machine; and their relationships with formal languages. Students will also learn about the limitations of computing machines.
At the end of the course, students should be able to:
Unit 1
Languages: Alphabets, string, language, basic operations on language, concatenation, union, Kleene star.
Unit 2
Regular Expressions and Finite Automata: Regular expressions, Deterministic finite automata (DFA).
Unit 3
Regular Languages: Non-deterministic Finite Automata (NFA), relationship between NFA and DFA, Transition Graphs (TG), properties of regular languages, the relationship between regular languages and finite automata, Kleene’s Theorem.
Unit 4
Non-Regular Languages and Context Free Grammars: Pumping lemma for regular grammars, Context-Free Grammars (CFG),
Unit 5
Context-Free Languages (CFL) and PDA: Deterministic and non-deterministic Pushdown Automata (PDA), parse trees, leftmost derivation, pumping lemma for CFL, properties of CFL.
Unit 6
Turing Machines and Models of Computations: Turing machine as a model of computation, configuration of simple Turing machine, Church Turing Thesis, Universal Turing Machine, decidability, halting problem.
Disclaimer: Details on this page are subject to change as per University of Delhi guidelines. For latest update in this regard please refer to the University of Delhi website here.