Contents

1. Preliminaries

1.1 Basic Concept of Language Theory

1.2 Relation

1.3 Principle Of Mathematical Induction

1.4 Solved Example

2. Finite Automata

2.1 Introduction

2.2 Finite Automata

2.3 Non-Deterministic Finite Automata

2.4 Equivalence of Deterministic and Non-Deterministic Fa

2.5 Finite Automata With e – Transitions

2.6 Conversion of e-Nfa to Dfa

2.7 Finite Automata With Output

2.8 Minimization of Dfa

2.9 Solved Examples

3. Regular Languages

3.1 Regular Expression (Re)

3.2 Regular Expression Identities

3.3 Equivalence of Finite Automata and Regular Expression (Re To Fa)

3.4 Pumping Lemma for Regular Language and Application

3.5 Closure Properties of Regular Languages

3.6 Solved Examples

4. Context Free Grammar and Languages

4.1 Fundamental Concepts of Grammar

4.2 Chomsky Hierarchy

4.3 Context Free Grammar

4.4 Ambiguous Grammar

4.5 Simplification of Cfg

4.6 Normal Forms

4.7 Regular Grammar

4.8 Closure Properties of Cfl’s

4.9 Solved Examples

5. Pushdown Automata

5.1 Introduction

5.2 Definition of Pda and Examples

5.3 The Languages of Pda

5.4 Dpda And Nfda

5.5 Equivalence of Pda and Cfg

5.6 Solved Examples

6. Turing Machine

6.1 Introduction

6.2 Turing Machine Model

6.3 Definition of Turing Machine

6.4 Language Accepted by Tm

6.5 Design of a Turing Machine

6.6 Non-Deterministic Turing Machines

6.7 Recursive Language

6.8 Types of Turing Machines

6.9 Turing Machine Limitations (Unsolvability)

6.10 Introduction to Lba and Csg

6.11 Solved Examples