DD2372 Automata and Languages

- Course Outline, Spring 2014 -

Class 1 [Book: Chapter 1]

• Introduction to Automata Theory
  
• Course goals and syllabus
• Course organization and administration
  
• The central concepts of Automata Theory

Part I: Finite Automata and Regular Languages

Class 2 [Book: 2.1, 2.2, 4.2.1, 4.3.2]

• Deterministic finite automata (DFA)
• Regular languages
• Closure properties of regular languages
• Complement construction
• Product construction
• Applications: model checking and runtime monitoring
  

Class 3 [Book: 2.3, 2.5]

• Nondeterministic finite automata (NFA)
• From DFA to NFA
• From NFA to DFA
• NFAs with epsilon transitions
• Handing out Assignment 1 (see Assignments)

Class 4 [Book: 3]

• Regular expressions (RE)
  
• From RE to NFA (constructions on epsilon-NFAs)
• From NFA to RE
• Kleene algebra

Class 5 [Book: 4.4]

• DFA state minimization
• Handing out Assignment 2 (see Assignments)
• Announcing Lab assignment 1 (see Labs)

Class 6 [Notes]

• Peer review of Assignment 1
• Peer review of Assignment 2
• Myhill-Nerode Theorem
• Application 1: Reasoning about DFA size
  

Class 7 [Book: 4.1, Notes]

• Application 2: Regular Inference and Adaptive Model Checking
• Cantor's Theorem, self-reference and limitations of automata
• The Pumping Lemma for regular languages
• Proving non-regularity using the Pumping Lemma
• Proving non-regularity using reduction
• Handing out Assignment 3 (see Assignments)

Part II: Context-Free Languages and Pushdown Automata

Class 8 

• Summary of Part I
• Introduction to Part II

Class 9 [Book: 5.1]

• Context-free grammars and languages
• Proving a CFG correct
• Regular languages are context-free
• Handing out Assignment 4 (see Assignments)

Class 10 [Book: 5.2, 5.4, Notes]

• Peer review of Assignment 3
• Peer review of Assignment 4
• Parse trees and derivations
• Ambiguity in CFGs

Class 11 [Book: 5.3, 7.2, 7.3, Notes]

• Chomsky-Schützenberger Theorem
• Applications of CFGs
• Modelling the behaviour of programs with recursion
• The Pumping Lemma for CFLs
• Handing out Assignment 5 (see Assignments)
• Announcing Lab assignment 2 (see Labs)

Class 12 [Book: 6.1, 6.2, 6.3]

• Peer review of Assignment 5
• Closure properties of CFLs (constructions on CFGs)
• Pushdown automata
• Acceptance on empty stack vs final states
• Equivalence of PDAs and CFGs

Class 13 [Book: 7.3.4, 6.4]

• Product of a PDA with a DFA
• Deterministic PDAs
• Summary of Part II
• Handing out Assignment 6 (see Assignments)

Part III: Turing Machines and Effective Computability

Class 14 [Book: 8.2, 8.4, 8.5, 9.1, 9.2]

• Peer review of Assignment 6
• Turing Machines and Recursively Enumerable Languages
• Limitations: encodings and Cantor's theorem
• Recurisive languages and decidability

Class 15 [Book: 9.3]

• Rice's theorem
• Other models of effective computability
• Course summary, outlook
• Exam preparation