Chapter 1: Introduction to the theory of computation

1.1 Mathematical Preliminaries and Notations

• Sets
• Functions and Relations
• Graphs and Trees
• Proof Techniques
• induction
• contradiction

1.2 Three Basic Concepts

• Languages 
• Grammers
• Definition: G = (V,T,S,P), V and T are nonempty and disjoint
• V is a finite set of objects called variables
• T is a finite set of objects called terminal symbols
• S in T, start variable
• P is a finite set of productions
• L(G), is the language generated by G.
• Automata: dfa and nfa