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.

Logistics
Time Mon 2-3pm and Thu, Fri 3-4pm
Location Classroom 4
Instructor Rachit Nimavat
TA None for this course
Contact (Please see Communication Policy below)
Office Hours Thu 4-5pm in the faculty room next to the library

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

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

  • Quizzes (Best 3 out of 4): 20%

  • Midsem: 30%

  • Endsem: 50%

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

Week Dates Topics Readings Slides/HWs
1 Jul28 - Aug1 Course Intro, Refresher on Basic Maths, Alphabet, Strings, and Languages Chapter 1 of ALC Lec-1, HW-0, Lec-2, Lec-3
2 Aug5 - Aug8 DFA and NFA Chapter 2 of ALC Lec-4, Quiz-1, Lec-5, Lec-6, Classwork-1
3 Aug12 - Aug14 NFA, Regular Expressions, and Kleene’s Theorem Chapters 2 and 3 of ALC HW-1, Lec-7, Lec-8
4 Aug18 - Aug22 Kleene’s Theorem and Pumping Lemma Chapters 3 and 4 of ALC Lec-9, Lec-10
5 Aug26 - Aug29 Pumping Lemma and Equivalence and Minimization of DFA Chapter 4 of ALC HW-2, Lec-11, Lec-12
6 Sep1 - Sep4 CFG, Parse Trees, and Ambiguity Chapter 5 of ALC Quiz-2, Lec-13, Lec-14
7 Sep8 - Sep12 Parsers, CNF, and PDA Chapters 5 and 6 of ALC Lec-15, Lec-16
8 Sep15 - Sep19 PDA Diagram, CFG=PDA, and Deterministic PDA Chapter 6 of ALC Lec-17, Lec-18, Classwork-2
9 Sep22 - Sep30 Midsem (No Classes) Midsem
10 Oct4 - Oct4 Pumping Lemma and Closure Properties Chapter 7 of ALC Lec-19
11 Oct6 - Oct10 Decision Properties, Context-Sensitive Languages, and Intro to TMs Chapters 7 and 8 of ALC Lec-20, Lec-21, Lec-22
12 Oct13 - Oct16 Languages of TM, Variations of TM, and Universal TM Chapter 8 of ALC Lec-23, Lec-24

Mistakes/typos/bugs in the content? Please let me know!

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

Other Resources

Acknowledgements

The Turing Machine lecture slides draws a lot of material from Pramod Ganapathi’s 2023 offering of CSE303: Introduction to the Theory of Computation.