This site is subject to update through the term. This page was last modified Thursday January 22, 2026 at 15:01:58 EST.
Time: MW 2:20pm - 3:35pm
Place: Copenhaver Band/Dance Facility, 324 Sumter St., Room 105
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.
| Class period | Spring 2025 | This semester |
| 1 | 2025-01-13 | 2026-01-12 |
| 2 | 2025-01-15 | 2026-01-14 |
| 2025-01-20 (no class; MLK Day) | ||
| 3 | 2025-01-22 (make-up class) | 2026-01-21 |
| 4 | 2025-01-27 | 2026-01-26 |
| 5 | 2025-01-29 | 2026-01-28 |
| 6 | 2025-02-03 | 2026-02-02 |
| 7 | 2025-02-05 | 2026-02-04 |
| 8 | 2025-02-10 | 2026-02-09 |
| 9 | 2025-02-12 | 2026-02-11 |
| 10 | 2025-02-17 | 2026-02-16 |
| 11 | 2025-02-19 | 2026-02-18 |
| 12 | 2025-02-24 | 2026-02-23 (Midterm 1) |
| 13 | 2025-02-26 | 2026-02-25 |
| 14 | 2025-03-03 | 2026-03-02 |
| 15 | 2025-03-05 | 2026-03-04 |
| 16 | 2025-03-17 | 2026-03-16 |
| 17 | 2025-03-19 | 2026-03-18 |
| 18 | 2025-03-24 | 2026-03-23 |
| 19 | 2025-03-26 | 2026-03-25 (Midterm 2) |
| 20 | 2025-03-31 | 2026-03-30 |
| 21 | 2025-04-02 | 2026-04-01 |
| 22 | 2025-04-07 | 2026-04-06 |
| 23 | 2025-04-09 | 2026-04-08 |
| 24 | 2025-04-14 | 2026-04-13 |
| 25 | 2025-04-16 | 2026-04-15 |
| 26 | 2025-04-21 | 2026-04-20 |
| 27 | 2025-04-23 | 2026-04-22 |
| 28 | 2025-04-28 | 2026-04-27 |
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 typeset 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 12 Course overview, strings, concatenation, baby automata | 2: Jan 14 DFAs, extended transition function |
| (MLK Day, no classes) | 3: Jan 21 String induction, intro to NFAs |
| 4: Jan 26 Formal NFAs, NFA simulation, computation paths, set-of-states construction (NFA -> DFA) | 5: Jan 28 e(psilon)-transitions,
e-NFAs, removing e-transitions (e-NFA ->
NFA) [Fall 2022 notes] [Homework 1 due] |
| 6: Feb 2 DFA minimization,
(in)distinguishable states, intro to regular
expressions
[Fall 2022 notes] [Homework 2 due] |
7: Feb 4 DFA min example, formal regexes, examples [Fall 2022 notes] |
| 8: Feb 9 Converting regexes to e-NFAs, intro to GNFAs [Fall 2022 notes] | 9: Feb 11 Formal GNFAs, state-elimination method (e-NFA -> regex) [Fall 2022 notes] |
| 10: Feb 16 e-NFA -> regex example,
proving some closure properties of reg langs (e.g., string reversal),
string homomorphisms [Homework 3 due] |
11: Feb 18 Closure under homom. and inverse homom. images, Pumping Lemma [Fall 2022 notes] |
| 12: Feb 23 Midterm 1 | 13: Feb 25 Proving a lang not regular, combining Pumping Lemma with closure properties |
| 14: Mar 2 Context-free langs and grammars, derivations | 15: Mar 4 CFGs for arith exprs & stmts, parse trees, ambiguity, regex -> CFG |
| Spring Break | Spring Break |
| 16: Mar 16 PDAs, examples, starting formal semantics (IDs, succession relation) | 17: Mar 18 PDA semantics (cont.):
initial ID, acceptance by final state equiv to acceptance by empty
stack; starting CFG -> PDA [Homework 4 due] |
| 18: Mar 23 CFG -> PDA: example, starting proof of correctness; restricted PDAs | 19: Mar 26 Midterm 2 |
| 20: Mar 30 Restricted PDA -> CFG; examples | 21: Apr 1 Intro to programming project; pumping lemma for CFLs [Programming Project Homepage] |
| 22: Apr 6 Closure properties of CFLs | 23: Apr 8 Intro to Turing machines
(TMs) [Homework 5 due] |
| 24: Apr 13 ; more on TMs: Church-Turing thesis; high-level algos, universal TM | 25: Apr 15 Decidability & undecidability; Turing-recognizability; undecidability of the Halting Problem, ATM |
| 26: Apr 20 The Editing Problem is
undecidable [Homework 6 due] |
27: Apr 22 ALLCFG is undecidable; intersection problem for CFGs is undecidable |
| 28: Apr 27 Review/Overflow | |
| May 4 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 Thursday January 22, 2026 at 15:01:58 EST.