CMPS 260 (Theoretical Foundations of Computer Science)
Spring 2025

Syllabus

Test/Quiz Information

• Final Exam (3pm on Wednesday, May 14)   preview
• Test #2 (April 16)
• Test #1 (March 10) preview

Homework Assignments

• Homework #1: Sets, Relations, Mealy Machines, DFAs  
• Homework #2: More DFA Design
• Homework #3: Nondeterministic Finite Automata
• Homework #4: Regular Expressions, Regular Language Closure Properties
• Homework #5: Context-free Grammars/Languages, q-grammars, CYK Algorithm   Sample solutions
• Homework #6: Turing machines, Countable Sets, Recursive/Recursively Enumerable Sets

Programming Assignments

• None yet.

Lecture Notes

• Introduction
• Some Laws of Sets and Logic
• Introduction to Finite State Machines by way of Mealy machines
• DFA examples from Lewis & Papadimitriou
• Some Examples of Finite Automata
• Subset Construction: Converting an NFA to a DFA   Example
• DFA Minimization   A second example
• Regular Expressions
• Linz Figures: Equivalence of FA's and Regular Expressions
• Linz Chapter 4
• Pumping Lemma for Regular Languages: Statement and Proof  
• Removing Useless Symbols from a CFG
• Exhaustive Breadth-first Parsing Algorithm for CFG's
• Notes on Left-to-Right Top-Down Parsing
• Proof of L(G) = {x∈{a,b}* | n_a(x) = n_b(x)}
• CFG to CNF: Algorithm and Example
• CYK Algorithm and Example
• PDA Examples
• CFL Closure Properties
• Pumping Lemma for CFL's
• Notes on Linz Chapters 9-12
• Notes on Linz Chapter 14

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