Theory of Computation (TOC)
AL-601-
Unit 1Introduction to Automata Theory
Examples of automata machines · Finite Automata as language acceptor and translator · Moore machines · Mealy machines · Composite machine · Conversion from Mealy to Moore and vice versa
-
Unit 2Types of Finite Automata
Non‑deterministic Finite Automata (NFA) · Deterministic Finite Automata (DFA) · Conversion of NFA to DFA · Minimization of automata · Regular expressions · Arden’s theorem · Language operations: union, intersection, concatenation, closure · Two‑way DFA
-
Unit 3Grammars
Types of grammar · Context‑sensitive grammar · Context‑free grammar (CFG) · Regular grammar · Derivation trees · Ambiguity in grammar · Simplification of CFG · Conversion of grammar to automata and vice versa · Chomsky hierarchy of grammars · Elimination of null and unit productions · Chomsky Normal Form (CNF) · Greibach Normal Form (GNF)
-
Unit 4Pushdown Automata
Examples of Pushdown Automata (PDA) · Deterministic PDA · Non‑deterministic PDA · Conversion of PDA to CFG and vice versa · CFG equivalent to PDA · Petri‑net model for PDA
-
Unit 5Turing Machines and Decidability
Construction techniques for Turing machines · Universal Turing machine · Multi‑tape, multi‑head and multidimensional Turing machines · NP‑complete problems · Decidable and recursively enumerable languages · Decidability · Undecidable languages · Halting problem · Post correspondence problem