Unit 3 : Automata Theory

Introduction: Alphabets, strings and languages. Finite automata and regular languages: deterministic and non-deterministic finite automata, regular expressions, regular languages and their relationship with finite automata, pumping lemma and closure properties of regular languages.

Unit 4

Context free grammars and pushdown automata: Context free grammars (CFG), parse trees, ambiguities in grammars and languages, pushdown automaton (PDA) and the language accepted by PDA, deterministic PDA, Non deterministic PDA, properties of context free languages, normal forms, pumping lemma, closure properties, decision properties.

Unit 5

Turing Machines: Turing machine as a model of computation, programming with a Turing machine, variants of Turing machine and their equivalence.