CMSC 28000: Introduction to Formal Languages (Winter 2020)

General information

Instructor: Timothy Ng (timng@uchicago.edu)
Office hours: MWF 2:30-3:30 or by appointment, JCL 203
Teaching assistants: Jafar Jafarov (jafarov@uchicago.edu)
Office hours: Mondays 4:00-5:00 pm, JCL 207; Jesse Stern (jesseastern@uchicago.edu)
Office hours: Tuesdays 12:00-1:00 pm, JCL 207
Lectures: MWF 1:30-2:30, Ryerson 276
Course webpage: https://cs.uchicago.edu/~timng/280/w20/

Overview

This course explores the mathematical foundations of computation. How do we quantify computational power? Are there limits on the kinds of problems that computers can solve? To answer such questions, we examine the curious connection between computation and mathematical linguistics.

Communication

There are a number of different ways we'll be communicating about the course.

Canvas will be used for announcements and confidential materials (solutions, grades).
Piazza will be used for questions and general discussion about course material.
Gradescope will be used for assignment submission and grading.
For confidential concerns, please e-mail me.

The Piazza and Gradescope sites for this course are accessible from Canvas. You should be automatically enrolled in Canvas, as well as Piazza and Gradescope, once you access these sites from Canvas.

Topics

Regular languages: Deterministic and non-deterministic finite automata, closure properties, regular expressions, pumping lemma, morphisms, DFA minimization, the Myhill-Nerode theorem.
Context-free languages: Context-free grammars, normal forms, pumping lemma for CFLs, pushdown automata, closure properties.
Decidable and undecidable languages: Turing machines, variations in the basic model (multi-tape, multi-head, non-determinism), Church-Turing thesis, undecidability, the halting problem, reductions.

Text

There is no required textbook for this course. Lectures will be roughly following Kozen. Automata and Computability (1997). Other good sources include Hopcroft and Ullman. Introduction to Automata Theory, Languages, and Computation, 1st ed. (1979) and Sipser. Introduction to the Theory of Computation, 3rd ed. (2012), though you should be careful about differences in notation. In addition, lecture notes will be made available shortly after each lecture.

Evaluation

Your computed grade in this course will be determined by the following formula: $$ \sum_{i=1}^8 (5\% \times P_i) + (20\% \times M) + \left( 40\% + \sum_{i=1}^8 (5\% \times (1-P_i)) \right) \times F,$$ where $P_i$ is the percentage grade for problem set $i$, $1 \leq i \leq 8$, $M$ is the grade for the midterm, and $F$ is the grade for the final.

In other words, there are eight problem sets worth up to 5% each, one midterm worth 20%, and a final exam worth at least 40%, with the portion of the grade that you don't receive on the problem sets reassigned to the final.

Lectures

January 6: Introduction, problems, strings
January 8: Languages, finite automata
January 10: Regular languages, closure properties
January 13: Product construction, nondeterminism
January 15: Nondeterministic finite automata, subset construction
January 17: $\varepsilon$-NFAs
January 22: Regular operations, regular expressions, equivalence with finite automata
January 24: Finite automata and regular expressions
January 27: Non-regular languages, the Pumping Lemma
January 29: The Myhill-Nerode theorem
January 31: DFA minimization
February 3: Brzozowski's DFA minimization algorithm.
February 5: Midterm test (in-class)
February 7: Derivatives of regular expressions, grammars
February 10: Context-free grammars
February 12: Chomsky Normal Form, the Cocke-Younger-Kasami algorithm
February 17: Pushdown automata
February 19: Equivalence of CFGs and PDAs
February 21: Non-context-free languages, the Pumping Lemma
February 24: Computability, Turing machines
February 26: Turing machines
February 28: Decidability and decision problems on formal languages
March 2: Recognizability and undecidability
March 4: Undecidable problems, Rice's theorem
March 6: Reduction, unrecognizability
March 9: Undecidable CFL problems, Post Correspondence Problem, Kolmogorov complexity
March 11: Q&A

Problem sets

Students are expected to write up solutions to problem sets individually, but may work together. Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.
Problem sets will be posted on Wednesdays and will be due on the following Wednesday at 6:00 pm (18:00).
We will be using Gradescope for assignment submission. Gradescope is accessible from Canvas. You should be automatically enrolled in Gradescope. If you aren't enrolled in Gradescope, please let me know immediately.
Please ensure that submissions are legible. See this guide for submitting on Gradescope.
Late submissions will not be accepted.

Problem set 1: Due Wednesday January 15
Problem set 2: Due Wednesday January 22
Problem set 3: Due Friday January 31
Midterm information: About the midterm and related exercises
Problem set 4: Due Wednesday February 12
Problem set 5: Due Wednesday February 19
Problem set 6: Due Wednesday February 26
Problem set 7: Due Wednesday March 4
Problem set 8: Due Wednesday March 11
Final exam information: About the final exam and related exercises

Academic integrity

It is your responsibility to be familiar with the University’s policy on academic honesty. Instances of academic dishonesty will be referred to the Office of the Provost for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.

Accessibility

Students with disabilities who have been approved for the use of academic accommodations by Student Disability Services (SDS) and need reasonable accommodation to participate fully in this course should follow the procedures established by SDS for using accommodations. Timely notifications are required in order to ensure that your accommodations can be implemented. Please meet with me to discuss your access needs in this class after you have completed the SDS procedures for requesting accommodations.