CMPS 260 (Theoretical Foundations of Computer Science)
Spring 2026

Syllabus

Test/Quiz Information

• Final Exam (3pm, May 20) preview
• Test #2 (April 15) preview   Sample Solutions
• Test #1 (March 27) preview Sample Solutions   Solution to old test

Homework Assignments

• Homework #1: DFA's     Sample Solutions
• Homework #2: Designing Mealy Machines   Sample Solutions
• Homework #3: Nondeterministic Finite Automata  Sample Solutions
• Homework #4: CFG/CFL; Top-Down Parsing; CYK Algorithm
• Homework #5: Devising Turing Machines

Programming Assignments

• None yet.

Webber text slides/notes

• Chapter 1: Fundamentals Webber slides   Notes
• Chapter 2: Finite Automata Webber slides   Notes
• Chapter 3: Closure Properties for Regular Languages Webber slides
• Chapter 5: Nondeterministic Finite Automata Webber slides
• Chapter 7: Regular Expressions Webber slides
• Chapter 8: Regular Expression Applications Webber slides
• Chapter 9: Advanced Topics in Regular Languages Webber slides
• Chapter 10: Grammars Webber slides
• Chapter 11: Nonregular Languages Webber slides
• Chapter 12: Context-free Languages Webber slides
• Chapter 13: Stack Machines Webber slides
• Chapter 16: Turing Machines Webber slides
• Chapter 17: Computability Webber slides
• Chapter 18: Uncomputability Webber slides   Notes

Lecture Notes

• Proof by Mathematical Induction
• Regular Languages:
  • Introduction to Finite State Machines by way of Mealy machines
  • Some Examples of Finite Automata
  • Subset Construction: Converting an NFA to a DFA   Example
  • Regular Language Closure Properties
  • DFA Minimization   A second example
  • Regular Expressions
  • Linz Figures: Equivalence of FA's and Regular Expressions
• Context-free Languages:
  • Some Examples of CFGs
  • Some CFG/CFL Decision Problems
  • CFG generating { x | #_a(x) = #_b(x) }
  • Removing Useless Symbols from a CFG
  • Exhaustive Breadth-first Parsing Algorithm for CFG's
  • Notes on Left-to-Right Top-Down Parsing
  • Computing FIRST and FOLLOW Sets
  • CFG to CNF (Chomsky Normal Form): Algorithm and Example
  • CYK Algorithm and Example
• NP-Completeness

Items of Interest

• Wikipedia entry for Finite-state machine
• Applications of DFA/FSM:
  • paper by Eric Gribkoff at UC Davis
  • presentation by Eric Gribkoff at UC Davis