Automata and Formal Languages


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.TopicsDirected ReadingLecture Notes
    1Sets, Languages, Logic Sipser pp1-34, p44-45 (up to example 1.11)PDF
    2Finite AutomataSipser pp35-62PDF
    3 Regular Expressions and LanguagesSipser pp63-76PDF
    4Minimal Deterministic Automata
    		PDF
    5Context Free LanguagesSipser pp77-100PDF
    6Non-Context Free LanguagesSipser pp99-100, pp115-119PDF
    7Pushdown AutomataSipser pp101-114PDF

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