Syllabus :
PDF.
Instructor :
Tao Jiang (jiangATcs.ucr.edu)
Office hours: MW 9:30-10:30am. Office:
WCH 336. The office hours will be held in-person this quarter, but online sessions might be possible upon special
requests (with pre-arrangement) and the Zoom meeting info can be found in the syllabus.
Teaching Assistants and office hours:
TA:
Lisa Chen (lchen314ATucr.edu).
Office hours: R 1:45-2:45pm, F 1-2pm.
TA: Yusen Zhang (yzhan677ATucr.edu).
Office hours: T 1-2pm.
Reader: Elena Hosseinmardi (ehoss003ATucr.edu).
Office hour: N/A.
Reader: Seokha Kang (skang121ATucr.edu).
Office hour: N/A.
TA office hours are held
in WCH 136 (mostly) or WCH 110 this quarter.
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 Skye Hall.
See its Tutorial Assistance Program homepage for more details.
Remote tutoring is also available by appointments.
Lectures:
MW 6:30-7:50pm, Student Sucess Center 235.
The lectures are offered only in-person, but the recordings of similar past lectures can be made available on Canvas/Yuja upon request.
Discussion Sections:
Dis 021, T 12:00 - 12:50pm, SSC 216, Lisa Chen/Yusen Zhang
Dis 022, T 6:00 - 6:50pm, Sproul 2340, Lisa Chen/Yusen Zhang
Dis 023, R 12:30 - 1:20pm, SSC 123, Lisa Chen/Yusen Zhang
Textbook:
Introduction to Automata Theory, Languages, and Computation, 3rd Edition by
J. Hopcroft, R. Motwani and J. Ullman, 2007, Pearson.
The book is available for purchase/rent via the Internet. Relevant chapters of the book can also be
found on eLearn/Canvas. The following webpage maintained by the authors of the textbook offers many errata and
sample solutions to
selected exercises:
Textbook Homepage
Reference Books:
Introduction to Formal Languages and Automata, 7th Edition, 2022, by
P. Linz and S. Ridger.
Foundations of Computing: An Accessible Introduction to Formal Languages, 2021, by C. Allison.
Introduction to Theory of Computation, 2019, by
A. Maheshwari and M. Smid.
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 to be used in lectures .
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
Computability
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 gives a technical
perspective on the question of how to decide the equivalence of NFAs
and could also be interesting to read:
The Equivalence Problem for Finite Automata
One may also find the following topic interesting:
The Smallest Grammar Problem
Homework Assignments:
HW1 and solutions
HW2 and solutions
HW3 and solutions
Midterm solutions
HW4 and solutions
HW5 and solutions
Please subscribe to the CS 150 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.