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