01
Unit 1: Finite Automata and Regular Languages
Introduction to the theory of computation, Alphabets, Strings, and Languages. Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA). Equivalence of NFA and DFA. Regular Expressions and their relationship with Finite Automata. Moore and Mealy Machines. Closure properties of regular languages.
02
Unit 2: Grammars and Properties of Regular Languages
Introduction to Formal Grammars and the Chomsky Hierarchy. Regular Grammars (Right-Linear and Left-Linear). The Pumping Lemma for Regular Languages, a tool to prove that a language is not regular. Minimization of Finite State Machines.
03
Unit 3: Context-Free Languages and Pushdown Automata
Context-Free Grammars (CFG): Derivations, Parse Trees, and Ambiguity in grammars. Pushdown Automata (PDA) as the machine model for CFGs. Deterministic vs. Nondeterministic PDAs. Simplification of CFGs (removing useless symbols, null productions, and unit productions). Normal Forms: Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).
04
Unit 4: Turing Machines
The Turing Machine (TM) as the ultimate model of computation. Formal definition, instantaneous description, and transition diagrams. Design of Turing Machines. Variants of Turing Machines (Multi-tape, Nondeterministic) and their equivalence to the standard model. The Church-Turing Thesis.
05
Unit 5: Undecidability and Complexity
Recursive and Recursively Enumerable Languages. The Universal Turing Machine. The concept of undecidability. The Halting Problem as a key undecidable problem. Introduction to computational complexity, the complexity classes P and NP, and the notion of NP-Completeness.