Automata, Logic, and Computation (CS 422): Fall 2025

Instructor:

Vinayak Prabhu

Office:

Office hours:

Email:

GTA:

Takwa Rhaimi

Email:

Office hours:

Course material on Canvas
Please do not use Canvas to contact me. Use MS Teams, or use my email, and prefix the subject line with "CS422:".

Course Description:

CS 422 is a core course in the foundations of computing. We will cover many of the central fundamental theoretical concepts underlying modern computing systems, without worrying about specifics of ever-changing programming languages and/or computing platforms. These concepts and techniques form the basis of core algorithms and frameworks in diverse application domains, eg., verification and testing, program analysis, circuit deign, cryptography, optimization, and models of computation. Here is a potential list of topics we will cover, and application domains you might encounter the concepts in.
- 1. Automata theory, regular languages (application domains: verification, testing, and control; program analysis; security; string processing; circuit design; models of computation, composing systems; compiler construction).
- 2. Grammars, pushdown automata, context-free languages (application domains: verification and testing; program analysis; compiler construction; NLP; models of computation).
- 3. Turing machines, decidability, reducibility (applications domains: limits of computation -- can a problem be solved by computers? program analysis; security; cryptography; verification and testing).
- 4. First order logic (application domains: verification and testing; security; AI; theorem proving; abstract reasoning).
Course focus: Our focus in the course will be on rigorous thinking and problem solving, based on the above topics. The types of problems can be found in the course textbook, which is very well written.
CS220 Background: We will revisit sets and propositional logic. These core concepts are crucial for many (most?) CS domains. While there will not be dedicated lectures on these topics, I will post references and will assign a couple of sections of readings for you to recall these concepts. Additionally, problems from these topics (sets and propositional logic) will appear in homeworks and exams, enabling you to practice and develop active skills in these areas. We will also discuss sticking points in lectures.

Textbook (required):

Introduction to the Theory of Computation by Michael Sipser.
Note: either the 3rd or the 2nd edition will suffice.

Note: Many of the homework problems will be from hardcover US versions (2nd or 3rd ed) of the course textbook.
For 3rd ed:
ISBN-13: 978-1133187790 ISBN-10: 113318779X
For 2nd ed:
ISBN-13: 978-0534950972 ISBN-10: 0534950973

Paperback international editions of the textbook have changed the order of the problems (this is standard practice unfortunately). If you have such a textbook, you will need to map homework problems to the appropriate ones in your book.

Additional References:

Mathematical Structures for Computer Science by Judith L. Gersting (7th edition).
This book is good for the CS220 background we will need. Sections from the textbook from the first chapter on Propositional and Predicate logic will be placed on electronic reserve.

Weekly Schedule (under revision)
Week	Topics	Assigned reading	Homework
8/25-8/29	Introduction, DFAs, Abstract Syntax Trees (AST) CS220 revisit (sets, Propositional logic),	MCS: Chapter 1, MCS: Sections 4.1,4.2,4.3; Chapter 0, Chapter 1 (till page 54)	Homework 0
9/02-9/05	DFAs, closure properties, CS220 revisit (sets, functions)	Chapter 1 till page 47	Homework 1
9/08-9/12	NFAs determinisation, subset construction	Chapter 1, Section 1.2, Gersting: Section 1.1	Homework 2, Prereq Quiz (Sets, Propositional logic)
9/15-9/19	Subset construction, Regular expressions	Chapter 1, Section 1.3	Homework 3
9/22-9/26	Regular expressions, CS220 revisit (Propositional logic), non-regular languages	Chapter 1, Gersting: Section 1.2	Homework 4
9/29-10/03	Pumping lemma and non-regular languages, Characterizing non-regular languages, First order logic, Henkin-Hintikka evaluation games, DFA minimization	Gersting: Sections 1.2, 1.3	Homework 5 (optional), Quarter-term: 1
9/26-9/30	Myhill-Nerode Theorem, Context-free grammars, review	Section 2.1	Midterm prep
10/03-10/05	Midterm 1, Pushdown automata	Section 2.2	Homework 6
10/10-10/14	Midterm 1 solutions, PDA-CFG equivalence	Section 2.3	Homework 7
10/17-10/21	Pumping lemma for CFLs, CYK algorithm, Turing machines	Chapter 3	Homework 8
10/24-10/28	Non-deterministic Turing machines, Undecidability	Chapter 4	Homework 9
10/31-11/04	Undecidability, Turing reducibility	Sections 5.1, 6.3	Midterm prep
11/07-11/11	Review, Midterm 2 (comprehensive)		Midterm prep
11/14-11/18	Many-one reducibility	Section 5.3	Homework 10
11/28-12/02	Midterm solutions, theories in first order logic, arithmetic heirarchy		Homework 11
12/05-12/09	Review
12/12-12/16	Final exam (open book)

Lectures:

Tuesday, Thursday, 5:00pm-6:15pm, CSB 130

Prerequisites:

The main prerequisite is the ability to reason at an abstract level (eg., CS220/320 or MATH366 or ECE312 or permission of the instructor).

Grading:

The course grade will be based on the following elements (minor adjustments to the weights may be made).

Homework. (weight 15%)
Prereq Quiz (basic 200 level material on sets, proofs, relations, functions). (weight 3%)
Quarter-term exam 1 (TBD). (weight 12%)
Quarter-term exam 2 (TBD). (weight 16%)
Quarter-term exam 3 (TBD). (weight 12%)
Quarter-term exam 4 (TBD). (weight 16%)
Final Exam (TBD). (weight 26%)

The final exam will be open (physical) book.

Homework and Readings:

Written homework will be regularly assigned (posted on Canvas) and you will be expected to solve the problems. You are also expected to read the relevant sections from the textbook.
Note: Posted lecture notes are not a substitute for textbook readings.

Homework Grading:

For each homework, you will either receive 50%, 75% or 100% points based on whether you have made a reasonable attempt at ⌈n/4⌉, ⌈n/2⌉, or ⌈3n/4⌉ problems respectively, where n is the number of problems in that homework. The reasonable attempt classification is not tied to correctness.

Late Homeworks:

Homeworks will typically be due at 5pm either on Tuesday or Thursday.

Life happens. For 2 (two) homeworks of your choosing, you can submit without penalty at the next lecture day by 5pm (eg, if a homework is due on Thursday, it can be submitted on Tuesday the next week). We will track the number of your late submissions.

Use of Generative AI Tools and Search Engines:

Treat these tools as if they were a person outside of class. Using these tools to understand content from lectures or the book is OK. Posting homework problems to obtain solutions/hints is not.

You may NOT post homework problems (or problems very similar to homework problems) to an AI tool or search engine in order to obtain solutions/hints. If you are copying substantial amounts of problem text into and out of a chat interface, or in a search engine, then you are in violation of this policy and compromising your education.

To quote one of my colleagues, use of AI tools to help with your homework is akin to asking your "super-kind, always-available, absolutely-no-ethics older sibling" to do the work for you.

Professional Conduct:

All students are expected to conduct themselves professionally. We, specifically the instructor and the GTA, assume you are familiar with the policies in the student information sheet for the department.

This course will adhere to the CSU Academic Integrity Policy as found in the Students' Responsibilities page of the CSU General General Catalog and in the Student Conduct Code. At a minimum, violations will result in a grading penalty in this course and a report to the Office of Student Resolution Center.

We work to maintain an environment supportive of learning in the classroom and laboratory. Towards that end, we require that you be courteous to and respectful of your fellow participants (i.e., classmates, instructor, GTA and any tutors). In particular:
- For on campus activities, please turn off the ring on your cell phone. If you are expecting an emergency call, sit near the door and slide out discretely to take it.
- In-class use of electronic devices in general, and laptops specifically, is permitted as a courtesy so that you may better participate and learn. If at any time the instructor judges that your use of an electronic device is becoming a distraction to others, you may be asked to turn it off and put it away.
- University labs (including but not limited to CSB 120) are professional spaces, and we expect professional behavior in these labs at all times.

Mental Health and Wellness:

CSU Health Network Mental Health Services has trained professionals who can help. Your student fees provide access to a wide range of mental health and well-being support services.

Call Mental Health Services at (970) 491-6053, and they will work together with you to find out which services are right for you.
CSU Health Network Mental Health Services

Student mental health and well-being resources
If you are concerned about a friend or peer, use Tell Someone by calling (970) 491-1350 or visiting Tell Someone to share your concerns with a professional who can discreetly connect the distressed individual with the proper resources. Reach out and ask for help if you or someone you know is having a difficult time.