This site is subject to update through the term. This page was last modified Wednesday January 29, 2025 at 14:04:51 EST.
Time: MW 2:20pm - 3:35pm
Place: Horizon Parking Garage, Room 210
This syllabus has basic course information, objectives, contacts, schedules, policies, etc.
I will post announcements here from time to time in reverse chronological order (most recent appearing first).
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 Blackboard.
| Mondays | Wednesdays |
| 1: Jan 13 Course overview, strings, concatenation, baby automata | 2: Jan 15 DFAs, extended transition function |
| (MLK Day, no classes) | 3: Jan 22 String induction, intro to NFAs |
| 4: Jan 27 Formal NFAs, NFA simulation, computation paths, set-of-states construction (NFA -> DFA) [Homework 1 due] [Answers] | 5: Jan 29 e(psilon)-transitions, e-NFAs, removing e-transitions (e-NFA -> NFA) [Homework 2 due date extended to Jan 31] [Fall 2022 notes] |
| 6: Feb 3 DFA minimization, (in)distinguishable states, intro to regular expressions [Fall 2022 notes] | 7: Feb 5 DFA min example, formal regexes, examples [Fall 2022 notes] |
| 8: Feb 10 Converting regexes to e-NFAs, intro to GNFAs [Fall 2022 notes] | 9: Feb 12 Formal GNFAs, state-elimination method (e-NFA -> regex) [Fall 2022 notes] |
| 10: Feb 17 e-NFA -> regex example, proving some closure properties of reg langs (e.g., string reversal), string homomorphisms [Homework 3 due] | 11: Feb 19 Closure under homom. and inverse homom. images, Pumping Lemma [Fall 2022 notes] |
| 12: Feb 24 Midterm 1 | 13: Feb 26 Proving a lang not regular, combining Pumping Lemma with closure properties |
| 14: Mar 3 Context-free langs and grammars, derivations | 15: Mar 5 CFGs for arith exprs & stmts, parse trees, ambiguity, regex -> CFG |
| Spring Break | Spring Break |
| 16: Mar 17 PDAs, examples, starting formal semantics (IDs, succession relation) | 17: Mar 19 PDA semantics (cont.): initial ID, acceptance by final state equiv to acceptance by empty stack; starting CFG -> PDA [Homework 4 due] |
| 18: Mar 24 CFG -> PDA: example, starting proof of correctness; restricted PDAs | 19: Mar 26 Midterm 2 |
| 20: Mar 31 Restricted PDA -> CFG; examples | 21: Apr 2 Intro to programming project; pumping lemma for CFLs [Programming Project Handout TBA] |
| 22: Apr 7 Closure properties of CFLs | 23: Apr 9 Intro to Turing machines (TMs) [Homework 5 due] |
| 24: Apr 14 ; more on TMs: Church-Turing thesis; high-level algos, universal TM | 25: Apr 16 Decidability & undecidability; Turing-recognizability; undecidability of the Halting Problem, A_TM |
| 26: Apr 21 The Editing Problem is undecidable [Homework 6 due] | 27: Apr 23 ALLCFG is undecidable; intersection problem for CFGs is undecidable |
| 28: Apr 28 Review/Overflow | |
| May 5 Final Exam, 12:30pm - 3:00pm |
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 Wednesday January 29, 2025 at 14:04:51 EST.