Introduction to Formal Languages and Automata Theory

Lecture, four hours; discussion, two hours; outside study, six hours. Enforced requisite: course 180. Designed for junior/senior Computer Science majors. Grammars, automata, and languages. Finite-state languages and finite-state automata. Context-free languages and pushdown story automata. Unrestricted rewriting systems, recursively enumerable and recursive languages, and Turing machines. Closure properties, pumping lemmas, and decision algorithms. Introduction to computability. Letter grading.

Review Summary

Clarity
8.3 / 10
Organization
8.3 / 10
Time
20+ hrs/week
Overall
8.3 / 10

Reviews

    Quarter Taken: Winter 2021 Online
    Grade: A

    Sahai bills his version of CS 181 as the unofficial "honors" offering, and he's right. It's very mathematical and proof-based. Each homework really does take about 20 hours (and that's probably a low estimate!). Definitely make sure you get a good study group that you can do the problems with, because you won't be able to do them all on your own.

    That being said, Sahai is an excellent lecturer. He starts with the basic question of "What is a computer, and what are the problems it can solve?" and organically builds upon concepts from there. You'll come away with a great understanding of how regular languages, finite automata, context-free grammars, and Turing machines all fit together. He also gives out extra credit for asking questions, so be sure to come to class ready to pay attention.

    The grade distribution is actually really generous – apart from giving out lots of extra credit in each lecture, you get extra credit for doing the homeworks in LaTeX and there extra credit problems on the midterm, final, and homeworks. I've heard that taking Math 115A helps a lot with the proof writing, but to be honest I found the TAs were pretty generous on grading for the HWs and tests. The final is also a week-long take-home final, due Friday of 10th week which is nice but also a little stressful. The class is curved, but extra credit applies after the curve so I think most of the class ended up with a B or above.

    The textbook is great and the class covers it at a pretty slow pace so there's not that much reading you have to do. Definitely read ahead if you want to get some extra credit tokens at the next lecture.

    All in all, this class will demand a lot of you, but if you really want to understand the theory of computation, I can't recommend this class enough.

    Quarter Taken: Winter 2022 In-Person
    Grade: A

    Great class!

Course

Instructor
Amit Sahai
Previously taught
23W 22W 21W 19W 18W 17W 16W 15W 14W 13W 12W 11W 10W 09W 05W

Grading Information

  • No group projects

  • Attendance required

  • 1 midterm

  • 10th week final

  • 100% recommend the textbook

Textbooks

Textbook information not available.