Theoretical Computer Science and Compiler Construction

Contents

1. Preliminaries

1.1 Sets

1.2 Basic definitions

2. Formal Languages

2.1 Introduction

2.2 Chomsky hierarchy of grammars

2.3 Kleene and positive closure

2.4 Operations on languages

3. Regular Languages

3.1 Introduction

3.2 Deterministic finite automata

3.3 Non deterministic finite automata

3.4 Finite automata with

3.5 NFA to DFA

3.6 Finite automata with output

3.7 Regular expressions

3.8 Equivalence of finite automata and regular expression

3.9 The myhill nerode theorem

3.10 The pumping lemma for regular sets

3.11 Closure properties of regular sets

4. Context Free Languages

4.1 Context free grammars (CFG)

4.2 Regular grammars

4.3 Pushdown automata