CS150 Homepage

Homework 4 has been posted and is due on Tuesday, Feb. 27.
Midterm solutions have been posted.
Homework 3 solutions have been posted.
Homework 2 has been returned.
Please subscribe to the class mailing list ASAP, via the link at the bottom of the page.

Syllabus : PDF

Instructor :

Tao Jiang (jiangATcs.ucr.edu)
Office hours: TuTh 4-5pm. Office: WCH 336.

Teaching Assistants and office hours:

Ashraful Arefeen (aaref001ATucr.edu). Office hours: W 1-2pm.
Dipan Shaw (dshaw003ATucr.edu). Office hours: F 2-3pm.
Reader: Chang Yuan (cyuan009ATucr.edu). Office hours: M 4-5pm.
Reader: Tong Shen (tshen021ATucr.edu). Office hours: M 4-5pm.
TA/reader office hours are held in WCH 110.

UCR Academic Resources Center (ARC):

It provides peer-led supplemental instruction, tutoring, writing support, and study skills workshops for students who want to excel in their studies, as well as for students who are having difficulty in their courses. The reception room for the ARC is located in Room 156 of the Surge Building. See its homepage for more details.


TuTh 5:10-6:30pm, Bourns Hall A125

Discussion Sessions:

Dis 021, T 1:10 - 2pm, Watkins 1111
Dis 022, W 2:10 - 3pm, Watkins 2240
Dis 023, R 8:10 - 9am, WCH 142


Introduction to Automata Theory, Languages, and Computation, 3rd Edition by J. Hopcroft, R. Motwani, and J. Ullman, 2006, Addison-Wesley.

The following webpage maintained by the authors of the textbook offers many errata and sample solutions to selected exercises and exams:
Textbook Homepage

Reference Books:

Introduction to Formal Languages and Automata, 6th Edition, 2017 by P. Linz
Introduction to the Theory of Computation, 3rd Edition, 2013 by M. Sipser

Lecture Notes:

Please download the following lecture notes and bring them to the lectures. The original lecture notes were provided at the textbook homepage courtesy of G. Grahne and J. Ullman, although extensive updates have been made by TJ.
Main lecture notes on automata and formal languages.

If you find working with a big set of slides intimidating, I have broken them up roughly according to our weekly topics below. However, these notes are not as up-to-date as the main notes. Please consult the tentative time table in the syllabus for the weekly schedule of our lectures and the chapters covered in the text and reference books.
Slides for week 1: Introduction, DFA and NFA.
Slides for week 2: REX and equivalence among DFA, NFA and REX.
Slides for week 3: Algebraic laws for REX and pumping lemma for RL.
Slides for week 4: RL properties and minimization of DFA.
Slides for week 5: CFG and CFL.
Slides for week 6: CFG parsing and ambiguity.
Slides for week 7: Various forms of PDA and their equivalence to CFG.
Slides for week 8: Chomosky normal form.
Slides for week 9: Pumping lemma, closure properties and the CYK algorithm.
Slides for week 10: Introduction to undecidability and Turing machines.

Here are two chapters that we wrote for the Algorithms and Theory of Computation Handbook some years ago:
Formal Grammars and Languages
These chapters are not very technical and may help provide some high-level concepts about the theory. The following article in a 2015 issue of Communications of the ACM provides some technical perspective on the question of how to decide the equivalence of NFAs and could also be interesting to read:
The Equivalence Prolem for Finite Automata

Homework Assignments:

Midterm solutions
HW3 and solutions.
HW2 and solutions, graded by the readers Chang and Tong.
HW1 and solutions. Q1-3 were graded by Tong and Q3-5 by Chang. Please visit their office hours on Monday for grading related questions.

Please subscribe to the CS150 class mailing list .

The following mapping shows how your overall scores will be translated into letter grades at the end of the quarter: 90+ -> A+, 85+ -> A, 80+ -> A-, 77+ -> B+, 73+ -> B, 70+ -> B-, 67+ -> C+, 63+ -> C, 60+ -> C-, 57+ -> D+, 53+ -> D, 50+ -> D-, 49- -> F.