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)