Syllabus :
PDF
Instructor :
Tao Jiang (jiangATcs.ucr.edu)
Office hours: TuTh 4-5pm. Office:
WCH 336.
Teaching Assistant and office hours:
Ei-Wen Yang (yyang027ATcs.ucr.edu)
Office hours: Wed. 2-3pm.
TA office hours are held in
WCH 110.
Lectures:
TR 2:10-3:30pm, INTN 1002
Discussion Sessions:
Dis 021, M 12:10 - 1pm, SPR 2339 (cancelled)
Dis 022, M 1:10 - 2pm, SPR 2339
Textbook:
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 , 5th Edition by
P. Linz
Introduction to the Theory of Computation, 1st Edition 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. 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: CNF and cloure properties of CFL.
Slides for week 9: Pumping lemma for CFL and CYK algorithm for membership.
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.
Homework Assignments:
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.