AD-501 Theory of Computation

Unit-I

Introduction of Automata Theory: Review of Sets, Mathematical formal proofs including proof by induction and by contradiction, Introduction to languages, grammars and automata: Alphabet, Representation of language and grammar, Types of Automata, Finite Automata as a language acceptor and translator, Moore machines and mealy machines, composite machine, Conversion from Mealy to Moore and vice versa.

Unit-II

Types of Finite Automata: Non-Deterministic Finite Automata (NDFA), Deterministic finite automata machines, conversion of NDFA to DFA, minimization of automata machines, regular expression, applications of regular expressions, Arden’s theorem. Meaning of union, intersection, concatenation and closure, 2 way DFA.

Unit-III

Grammars: Types of grammar, context sensitive grammar, and context free grammar, regular grammar. Derivation trees, ambiguity in grammar, simplification of context free grammar, conversion of grammar to automata machine and vice versa, Chomsky hierarchy of grammar, Chomsky normal form and Greibach normal form.

Unit-IV

Push down Automata: example of PDA, deterministic and non-deterministic PDAs, Context Free Grammar, Parsing, Ambiguity, Normal form of CFGs, CFG to NPDA, NPDA to CFGs CFG equivalent to PDA, Petri nets model.

Unit-V

Turing Machine: Turing Machine as acceptor, Recognizing a Language, Universal TMs, Linear Bounded Automata, Context Sensitive Languages, Recursive and Recursively Enumerable Languages, Unrestricted Grammars. Halting problem of Turing machine & the post correspondence problem, Concept of Solvability and Unsolvability, Church’s Thesis, Complexity Theory – P and NP problems.

Notes

Assignments Session 2025-26 (ODD)(Batch: 2023-2027)