Formal languages and automata theory Lectures

(Click to Download PPT)

PART I:  Finite Automata and Regular Languages

  • Lecture 1.  Introduction (ppt)
  • Lecture 2.  Deterministic Finite Automata (DFAs) (ppt)
  • Lecture 3.  Nondeterministic Finite Automata (NFAs) (ppt)
  • Lecture 4.  Patterns, regular expressions and Finite Automata (ppt)
  • Lecture 5.  Klenee algebras and regular expressions (skipped)
  • Lecture 6.  Homomorphisms(ppt)
  • Lecture 7.  Limitations of Finiter Automata(ppt)
  • Lecture 8.  DFA state minimization (ppt)
  • Lecture 10 The Myhill-Nerode Theorem(ppt)

PART II: Pushdown Automata and Context-Free Langugaes

  • Context-Free Grammars and Langugaes(ppt)
  • Linear Grammars and Normal Forms(ppt)
  • Pushdown Automata and CFGs(ppt)
  • Parse Trees and Parsing(ppt)
  • The Pumping lamma and properties of CFLs(ppt)

PART III: Turing machines and Effective Computability

  • Turing Machines and the Church-Turing thesis(ppt)
  • Other equivalent models of Turing machines (ppt)
  • Problem reduction and Other Undecidable Problems(ppt)

No comments: