CMPS 260 (Theoretical Foundations of Computer Science)
Spring 2026

Syllabus

Test/Quiz Information

• Test #2 (April 15) preview
• 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

Programming Assignments

• None yet.

Webber text slides/notes

• Chapter 1: Webber slides   Notes
• Chapter 2: 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
  • CYK Algorithm and Example

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