3. Theory of Computation

---

3. Theory of Computation

3.1 Formal Languages and Grammars

• Backus–Naur Form (BNF)

• Languages and Their Classifications

• Grammars: Regular, Context-Free, Context-Sensitive, Unrestricted

---

3.2 Finite Automata

• Deterministic Finite Automata (DFA)

• Non-Deterministic Finite Automata (NDFA)

• Regular Expressions

• Regular Grammar

---

3.3 Closure Properties and Homomorphism

• Closure Properties of Regular Languages

• Homomorphism and Its Applications

---

3.4 Pigeonhole Principle and Pumping Lemma

• Pigeonhole Principle in Computation

• Pumping Lemma for Regular Languages

• Applications of Pumping Lemma

---

3.5 Context-Free Grammars and Parsing

• Context-Free Grammars (CFGs)

• Parsing Techniques

• Ambiguity in Grammars

---

3.6 Pushdown Automata

• Pushdown Automata (PDA)

• Non-Deterministic Pushdown Automata (NPDA)

• Equivalence of NPDA and CFGs

---

3.7 Turing Machines and Complexity Theory

• Turing Machines: Definition and Models

• Universal Turing Machine

• Complexity Theory Overview

• Classes P and NP

---