Part I: Foundations

Introduction

Chapter 1: Mathematical Preliminaries

1.1 Sets

1.2 Relations

1.3 Functions

1.4 Logic

1.5 Graphs and Trees

Chapter 2: Introduction to Formal Languages

2.1 Symbols, Alphabets, Strings, and Languages

2.2 Grammars

2.3 Automata

Part II: Regular Languages and Finite Automata

Chapter 3: Finite Automata

3.1 Finite Automata: Formal Definition

3.2 Acceptability of Strings

3.3 Language of Finite Automaton

3.4 Types of Finite Automata

3.6 Deterministic Finite Automata

3.7 Designing DFA: Examples (1-5)

3.8 Designing DFA: More Examples (6-10)

3.9 Designing DFA: Examples (11-15)

3.10 Nondeterministic Finite Automata

3.11 NFA with ε-Transitions

3.12 Finite Automata with Output

3.13 Minimization of DFA

Chapter 4: Regular Expressions

4.1 Regular Expressions

4.2 Regular Language

4.3 RE to FA Conversion (Thompson’s Construction)

4.4 FA to RE Conversion (Arden’s Theorem)

4.5 Regular Expression Identities

Chapter 5: Properties of Regular Languages

5.1 Pumping Lemma for Regular Languages

5.2 Closure Properties of Regular Languages

Part III: Context-Free Languages and Pushdown Automata

Chapter 6: Context-Free Grammars

6.1 Context-Free Grammars

6.2 Ambiguity in CFGs

6.3 Simplification of CFGs

6.4 Normal Forms

Chapter 7: Pushdown Automata

7.1 Pushdown Automata

7.2 PDA Acceptance

7.3 Deterministic and Non-Deterministic PDA

7.4 CFG to PDA Conversion

7.5 PDA to CFG Conversion

Chapter 8: Properties of Context-Free Languages

8.1 Pumping Lemma for Context-Free Languages

8.2 Closure Properties of Context-Free Languages

8.3 Decision Properties of Context-Free Languages

Part IV: Turing Machines and Computability

Chapter 9: Turing Machines

9.1 Turing Machine Model

9.2 Turing Machine Design

9.3 Language Accepted by TM

9.4 Types of Turing Machines

Chapter 10: Undecidability

10.1 Church-Turing Thesis

10.2 Undecidable Problems

10.3 Reducibility