Topics covered: Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to computability and unsolvability (Turing machines) and computational complexity. The course will be divided into three phases:
First phase (roughly 3 weeks): Formal languages; finite automata and regular expressions; properties of regular languages; pumping lemma for regular languages.
Second phase (roughly 2 weeks): Pushdown automata and context-free grammars; properties of context-free languages; pumping lemma for context-free languages.
Third phase (roughly 4 weeks): Introduction to computability (Turing machines); unsolvability; computational complexity.
Pre-requisites. CS 40 with a grade C or better.
Text Book. Introduction to the Theory of Computation by Michael Sipser. Second or third edition is fine. It's available on Amazon.
Lecture hours: Tuesdays and Thursdays 12:30pm to 1:45pm
Lecture hall: Embarcadero Hall
First day of lecture:
Instructor: Prabhanjan Ananth
Instructor's office hours: Thursdays, 2pm to 3pm, HFH 1119
Digital communication with the instructor: via Slack only.
TA office hours: TBD
ULA office hours: TBD
Discussion Sections:
Fridays, 1-1:50pm (ELLSN 2626)
Fridays, 2-2:50pm (GIRV 2128)
First day of discussion sections: Aprl 3rd
Sections from the Introduction to the Theory of Computation (third edition) are posted below.
March:
31st: Introduction to the course, administrivia, discrete math basics. (Section 0.2)
April:
2nd: Introduction to finite automata (Section 1.1)
7th: Non-deterministic finite automata (Sections 1.1, 1.2)
9th: Equivalence of NFAs and DFAs (Section 1.2)
14th: Closure Properties (Section 1.2)
16th: Regular Expressions (Section 1.3)
21st: Pumping lemma for regular languages (Section 1.4)
23rd: Context-free grammars (Section 2.1)
28th: Pushdown automata (Section 2.2)
30th: Equivalence of pushdown automata and context-free grammars (Section 2.2)
May:
5th: Pumping lemma for context-free languages (Section 2.3)
7th: Midterm
12th: (guest lecture) Turing machines: formal definition (Section 3.1)
14th: (guest lecture) Turing machines: examples (Section 3.1)
19th: More examples, Multi-tape Turing machines, Non-deterministic Turing machines, Enumerators (Section 3.2)
21st: Cantor's diagonalization method (Section 4.2)
26th: Unrecognizable and undecidable languages (Section 4.2)
28th: Unrecognizable and undecidable languages - cont'd, reductions (Section 5.1)
June:
2nd: Unrecognizable and undecidable languages - cont'd, reductions (Section 5.1)
1st Assignment:
Release date: 8th April (2nd week)
Due date: 15th April (3rd week)
Graded assignments released: end of 4th week
2nd Assignment:
Release date: 22nd April (4th week)
Due date: 29th April (5th week)
Graded assignments released: end of 6th week
3rd Assignment:
Release date: 20th May (8th week)
Due date: 27th May (9th week)
Graded assignments released: end of 10th week
Midterm: 7th May (Thursday) during lecture hours.
Location: Embarcadero Hall
Graded midterms released: end of 7th week
Finals: 11th June, 12pm to 3pm.
Location: TBD
Grading instructions:
Assignments contribute towards 40% of the grade
Midterm contributes towards 30% of the grade
Finals contribute towards 30% of the grade
Grading will be curved.
Assignment instructions:
Assignment submissions need to be made on Gradescope. The gradescope code is: 6X6B7X.
The assignment schedule has been announced well in advance. Please mark the schedule in your calendar accordingly. No assignment extensions will be allowed.
No collaboration allowed on assignments. Discussing the solutions of the assignment with your fellow classmates before the due date is strictly prohibited. Please read the UCSB policy here.
Consulting the internet for solutions (including posting questions on Chegg) is strictly prohibited. In particular, the use of Artificial Intelligence tools (including LLMs such as ChatGPT) is strictly prohibited.
Any medical reason for not being able to complete the assignments should be accompanied by a doctor's note. Read more about absence and withdrawal from a course here.
Exam instructions:
Please bring pens, pencils to the exam. We will provide solution booklets for you.
Discussing with your classmates during the exam time is strictly prohibited.
Please be on time. Please read the UCSB policy here.
Other instrutctions:
All announcements will be made on Slack. If you have enrolled in the course, the Slack link to join the course workspace will be sent to you via email.
If your grades are poor in the assignments or the exames then I suggest you re-do the assignment and submit it to the TAs by the end of 10th week. This doesn't necessarily improve the grade but could ensure that you won't fail in the course.