CMSC/MATH 28000: Introduction to Formal Languages

Course Description

This course is a basic introduction to computability theory and formal languages. Topics include automata theory, regular languages, context-free languages, and Turing machines.

Class schedule: TR 9:00 - 10:20 AM at Ryerson 251

Midterm: Feb. 10 (Tuesday) 9:00 - 10:20 AM at Ryerson 251

Instructor: Ketan Mulmuley (mulmuley@uchicago.edu)

Teaching assistant: Yuan Li (yuanli@cs.uchicago.edu) and Ridwan Syed (rsyed@uchicago.edu)

Grading: homework 40%, midterm 20%, final 40%

Textbook

Automata Theory, Languages, and Computation, 3rd edition, by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, published by Addison-Wesley.

Office Hours

Ketan Mulmuley: Monday 4:00-5:00 pm, Ryerson 165B

Yuan Li: Wednesday 4:00-5:00 pm, Ryerson 162B

Tutorial

There will be a weekly tutorial on Thursday 5:00 - 6:00 pm at Ryerson 277.

Homeworks

Each week, homeworks will be posted on Friday, and due on Thursday's class. You need to hand in your homework on Thursday's class.

Late homeworks may not be accepted.

  • Assignment #1, due January 15, graded by Yuan
  • Assignment #2, due January 22, graded by Ridwan
  • Assignment #3, due January 29, graded by Yuan
  • Assignment #4, due February 5, graded by Ridwan
  • Assignment #5 [solution], due February 12, graded by Yuan
  • Assignment #6, due February 19, graded by Ridwan
  • Assignment #7 [solution], due February 26, graded by Yuan
  • Assignment #8, due March 5, graded by Ridwan
  • Assignment #9, due March 12, graded by Yuan

    • Lecture Notes

    The notes are taken by students or teaching assistant. Not proofread by instructor.

  • Lecture 1: Finite State Automaton
  • Lecture 2: Regular Expression
  • Lecture 3: Two-way DFA
  • Lecture 4: Properties of Regular Language
  • Lecture 5: Myhill-Nerode Theorem
  • Lecture 6: Context-Free Grammar
  • Lecture 7: Greibach Normal Form
  • Lecture 8: Pushdown Automaton
  • Lecture 9: Properties of CFL
  • Lecture 10: Properties of CFL, cont.
  • Lecture 11: Decision Problems for CFLs
  • Lecture 12: Undecidability
  • Lecture 13: Turing Machine
  • Lecture 14: Recursive Languages
  • Lecture 15
  • Lecture 16
  • Lecture 17