This site is subject to update through the term. This page was last modified Thursday April 11, 2024 at 13:30:32 EDT.
Time: MW 2:20pm - 3:35pm
Place: Davis College, Room 209
This syllabus has basic course information, objectives, contacts, schedules, policies, etc.
A lecture link will usually become active shortly before the time of the next lecture.
Here are my hand-written lecture notes from Apr 10 to Apr 24, 2023.
Here are my hand-written lecture notes from Mar 20 to Apr 5, 2023.
Here are my hand-written lecture notes from Mar 13 to Mar 15, 2023.
Here are my hand-written lecture notes from Feb 22 to Mar 1, 2023.
Here are my hand-written lecture notes from Feb 1 to Feb 15, 2023.
Here are my hand-written lecture notes for January 2023.
I will do my best to keep my COURSE NOTES current for the lectures. The date of the last update appears below my name on the title of the first page.
Dates link to the handwritten notes I wrote in lecture in Spring 2022. (See above for links to this semester's lectures.) I will likely stick reasonably close to the same notes for this semester, although some variation is inevitable. Links to homework handouts are located on the day they are due. Submit your homework before 11:30pm through CSE Dropbox.
| Mondays | Wednesdays |
| 1: Jan 8 Course overview, strings, concatenation, baby automata | 2: Jan 10 DFAs, extended transition function |
| (MLK Day, no classes) | 3: Jan 17 String induction, intro to NFAs |
| 4: Jan 22 Formal NFAs, NFA simulation, computation paths, set-of-states construction (NFA -> DFA) [Homework 1 due] [Answers] | 5: Jan 24 e(psilon)-transitions, e-NFAs, removing e-transitions (e-NFA -> NFA) [Homework 2 due] [Fall 2022 notes] |
| 6: Jan 29 DFA minimization, (in)distinguishable states, intro to regular expressions [Fall 2022 notes] | 7: Jan 31 DFA min example, formal regexes, examples [Fall 2022 notes] |
| 8: Feb 5 Converting regexes to e-NFAs, intro to GNFAs [Fall 2022 notes] | 9: Feb 7 Formal GNFAs, state-elimination method (e-NFA -> regex) [Fall 2022 notes] |
| 10: Feb 12 e-NFA -> regex example, proving some closure properties of reg langs (e.g., string reversal), string homomorphisms [Homework 3 due] | 11: Feb 14 Closure under homom. and inverse homom. images, Pumping Lemma [Fall 2022 notes] |
| 12: Feb 19 Midterm 1 | 13: Feb 21 Proving a lang not regular, combining Pumping Lemma with closure properties |
| 14: Feb 26 Context-free langs and grammars, derivations | 15: Feb 28 CFGs for arith exprs & stmts, parse trees, ambiguity, regex -> CFG |
| Spring Break | Spring Break |
| 16: Mar 11 PDAs, examples, starting formal semantics (IDs, succession relation) | 17: Mar 13 PDA semantics (cont.): initial ID, acceptance by final state equiv to acceptance by empty stack; starting CFG -> PDA [Homework 4 due] |
| 18: Mar 18 CFG -> PDA: example, starting proof of correctness; restricted PDAs | 19: Mar 22 Midterm 2 |
| 20: Mar 25 Restricted PDA -> CFG; examples | 21: Mar 27 Intro to programming project; pumping lemma for CFLs [Programming Project Handout] |
| 22: Apr 1 Closure properties of CFLs | 23: Apr 3 Intro to Turing machines (TMs) [Homework 5 due] |
| 24: Apr 8 ; more on TMs: Church-Turing thesis; high-level algos, universal TM | 25: Apr 10 Decidability & undecidability; Turing-recognizability; undecidability of the Halting Problem, A_TM |
| 26: Apr 15 The Editing Problem is undecidable [Homework 6 due] | 27: Apr 17 ALLCFG is undecidable; intersection problem for CFGs is undecidable |
| 28: Apr 22 Review/Overflow | |
| April 29 Final Exam, 12:30pm - 3:00pm |
I will post announcements here from time to time in reverse chronological order (most recent appearing first).
There are a number of good alternate textbooks for this material. The one I use for the graduate-level version of this course (CSCE 551) is Michael Sipser, Introduction to the Theory of Computation (Third Edition). Cengage Learning, 2013. There is a fair amount of overlap between the two classes, and Sipser's book gives a fresh, concise take on the subject. I like this text the best.
For a gentle introduction to proof techniques, I recommend the free, online book Book of Proof by Richard Hammack (2009). Much of what we do in the first couple of weeks is done in more depth in this book.
JFLAP is a free Java-based program for simulating and manipulating automata and Turing machines. Go to http://www.jflap.org, where you'll have the opportunity to download the software (JFLAP.jar, requiring Java 1.4 or later, last I checked).
This page last modified Thursday April 11, 2024 at 13:30:32 EDT.