Automata and Formal Languages PDF SLIDES Sipser Michael, Introduction to the Theory of Computation

Automata and Formal Languages PDF Slides

Recommended Books

1. Sipser Michael, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
2. Hopcroft J, Motwani R and Ullman J, Introduction to Automata Theory, Languages and Computation (2nd ed), Addison-Wesley, 2001.
3. Kozen Dexter C., Automata and Computability, Springer-Verlag, 1997

Topics Covered

1. Finite Automata (Reif note 3, Reily note 2)
   • Formal definition and examples
   • Design of FA
   • Definition of DFA and NFA
   • Equivalence of NFAs and DFAs
   • Regular operations and closure
2. Regular Expressions and Languages (Reily note 3)
   • Definition of a regular expression
   • Definition of non-regular languages
   • Equivalence between regular language and finite automaton
   • The pumping lemma for regular languages
3. Context-Free grammars (Reif note 4, Reily notes 5--6)
   • Formal definition and examples
   • Design of context-free grammars
   • Ambiguity
   • Chomsky normal form
   • Non-context-free languages definition and examples
   • Pumping lemma for CFLs
4. Pushdown Automata (PDA) (Reif note 5, Reily note 7)
   • Definition and examples
   • Converting a CFG to a PDA
5. Turing machines (Reif note 6)
   • Formal definition and examples
6. Decidability
   • Decidability and undecidability
   • The Church-Turing Thesis
   • Undecidability of the Halting problem 
   
   
   Lecture Slides download here
   
   

   No.	Topics	Directed Reading	Lecture Notes
   1	Sets, Languages, Logic	Sipser pp1-34, p44-45 (up to example 1.11)	PDF
   2	Finite Automata	Sipser pp35-62	PDF
   3	Regular Expressions and Languages	Sipser pp63-76	PDF
   4	Minimal Deterministic Automata		PDF
   5	Context Free Languages	Sipser pp77-100	PDF
   6	Non-Context Free Languages	Sipser pp99-100, pp115-119	PDF
   7	Pushdown Automata	Sipser pp101-114	PDF

   
   

   No.	Topics	Directed Reading	Lecture Notes
   1	Introduction	Sipser, Chapter 0	PDF
   2	Mathematical Notations for Computations	Sipser, Chapter 0, pages 3-25	PDF
   3	Finite State Automata (FSAs)	Sipser, Chapter 1, pages 31-83	PDF
   4	PDAs / CFLs, Part 1: Context Free Grammars	Sipser, Chapter 2.1, pages 91-100	PDF
   5	PDAs / CFLs, Part 2: Pushdown Automata	Sipser, Chapter 2.2, pages 101-104	PDF
   6	Turing Machines	Sipser, Chapters 3.1, 3.2, pages 125-141. See also Biography of Alan Turing	PDF
   7	Decidability, Part 1: Decidable Problems	Sipser, Chapter 3.3, pages 142-147, Chapter 4.1, pages 151-156	PDF
   8	Decidability, Part 2: The Halting Problem	Sipser, Chapter 4, pages 151-168	PDF