CS 304: Automata and Formal Language (Monsoon 2025)
For official announcements, grade postings, and assignment submissions, please use the official course page on Google Classroom. This page serves as the main syllabus and schedule.
Quick-links to Schedule and Resources.
Logistics
| Time | TBD |
| Location | TBD |
| Instructor | Rachit Nimavat |
| TA | None for this course |
| Contact | [email protected] (Please see Communication Policy below) |
| Office Hours | TBD (These are drop-in sessions for conceptual questions) |
Course Description
Welcome to Automata and Formal Language course! This course is aimed at second-year undergraduate students. The goal is to introduce the theoretical foundations of computer science by studying formal languages and the abstract machines that compute them. The course will cover the hierarchy of computation from simple models to universal machines. We intend to cover the following topics (detailed summary):
- Finite Automata and Regular Languages
- Context-Free Grammars and Pushdown Automata
- Turing Machines and Computability
- Computational Complexity
Expected Outcomes
- Ability to design automata, grammars, and Turing machines for specified languages.
- Understanding of the correspondence between different machine models and classes of formal languages.
- Ability to write formal proofs regarding properties of languages and computation.
- Familiarity with the fundamental limits of what is computable and the distinction between tractable and intractable problems.
Prerequisites
-
CS 101: Fundamentals of Computer Programming You should be very comfortable with fundamental data structures (lists, trees), basic algorithms (sorting, searching), and recursion (recursion).
-
Mathematical Maturity Success in this course depends on your ability of Algorithmic Thinking (how to break down a problem into a sequence of logical steps) and Abstractions (how to think about problems without getting lost in implementation details). While we will discuss writing formal proofs in class, a solid foundation in mathematical reasoning is expected.
Grading (Tentative)
Your final grade will be based on the following components. This breakdown is tentative and is subject to approval by the senate.
- Quizzes (3-4): 20%
- Homework Assignments (3-4): 30%
- Midterm Exam: 25%
- Final Exam: 25%
- Scribing Notes / Grading Assignments: 10% bonus
Course Policies
Communication Policy
- Google Classroom is the primary channel for all official announcements, grade postings, assignment submissions, and discussions/queries regarding course content, homework, or logistics. I strongly encourage you to answer each other’s questions!
- Email is reserved for personal matters, such as discussing grades or personal emergencies. I will do my best to respond within a day.
Collaboration Policy
In a large, theoretical course, learning from your peers is one of the most effective tools for success. I strongly encourage you to discuss homework problems, explore general concepts, and share ideas with your classmates. You are even encouraged to use tools like Large Language Models (LLMs): this is how professionals work. However, your submitted write-up must be your own work. This means:
- You must write up your solutions independently, without looking at another student’s write-up or consulting any resource that provides direct solutions.
- You must cite any collaborators (including LLMs, if any) you discussed the problems with at the top of your submission. Briefly describe the nature of the discussions.
Rule of thumb: You should be able to reproduce and explain your entire solution on your own if/when asked.
Late Submission Policy
No Extensions, so plan accordingly! We’ll drop the lowest scored homework. For major personal or medical emergencies, please contact me to make arrangements.
Academic Integrity
Our community is built on trust and academic honor. Any form of cheating, plagiarism, or misrepresentation of your work is a serious violation of that trust. Such an act of academic dishonesty will result in a failing grade for the course and will be reported to the senate.
Schedule
This schedule is tentative and will be updated weekly with links to lecture notes and readings.
| Week | Dates | Topics | Readings | Notes/Slides |
|---|---|---|---|---|
| 1 | Jul28 - Aug1 | Course Intro, Refresher on Basic Maths, Alphabet, Strings, and Languages | Chapter 1 of ALC |
Textbook and Resources
I wil provide self-contained lecture notes and other resources for all topics covered in this course. You are not required to purchase the textbook, but you may find it useful to consult a physical copy, for which 5 copies are available for in-library use.
Textbook
- [ALC] John E. Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd edition (1 January 2008); Pearson India
Other Resources
- Michael Sipser. Introduction to the Theory of Computation, Cengage Learning, 3rd Edition, 2013.
- Theory of Computation course by Prof. Michael Sipser, MIT OpenCourseWare.
- Other resources and papers as linked in the schedule.
The Back Bench
This official unofficial corner is for the whispers, the doodles, and the inside jokes! Share your best course-related memes/jokes/trivia/reels here and give everyone a reason to laugh.
- Let’s kick off with a classic comic that captures the funnier side of thinking like a programmer. Welcome to the club! A Bunch of Rocks.