Formal Languages and Automata

Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Wednesdays 1pm-3pm, Bahen 1240 (and Zoom)
Office Hours: Wednesdays 11am-12noon (on Zoom)
TA: Harry Sha
Tutorials: Friday 1pm-2pm, Bahen 1240 (and Zoom)
TA Office hours: Mondays 4:30pm-5:30pm (on Zoom)

Please use the course piazza site for questions.


Text book: Introduction to the Theory of Computation, 3rd Edition (by Sipser).

This course will study primitive (and beyond) mathematical models for computers, and how to understand the power and limitations of these models. Topics include: Regular Languages, Finite Automata, Regular Expressions, Context-Free Languages, Context-Free Grammars, Pushdown Automata, Computability Theory, Turing Machines, Undecidability and a taste of Computational Complexity Theory. This course will need comfort with proofs and mathematical precision.

• Finite automata and regular languages - 3 weeks
• Context free grammars and push-down automata - 3 weeks
• Turing Machines, the Church-Turing Thesis, Undecidability - 4 weeks
• Miscellaneous advanced topics - 2 weeks

Homeworks

• HW0
• Remaining homework on quercus page.

Lectures

• September 15: Languages, DFAs, NFAs, Closure properties of regular languages
• September 22: September 22: Regular expressions, equivalence of DFAs and regular expressions, some languages are not regular
• September 29: The pumping lemma, applications, CFGs
• October 6: More CFGs, efficient parsing, pushdown automata
• October 13: equivalence between CFGs and PDAs, non-CFLs
• October 20: between regular languages and CFGs
• October 27: midterm
• November 3: Turing Machines
• November 10: NO CLASS - Fall break
• November 17: Variants of Turing Machines, undecidability
• November 24: Reductions
• December 1: Guest lecture by Prof. Ben Rossman - Circuit Complexity
• December 8: Kolmogorov Complexity