EECS20N: Signals and Systems

Instructor Guide for Week 4

The fourth week deals with nondeterminism and equivalence in state machines. Equivalence is based on the notion of simulation, so simulation relations and bisimulation are defined for both deterministic and nondeterministic machines. These are used to explain that two state machines may be equivalent even if they have a different number of states, and that one state machine may be an abstraction of another, in that it has all input/output behaviors of the other (and then some).

Problem session

  • Review problem 9 of chapter 2 (renumbered problem 8 after Sp 2000), which was assigned in the previous problem set. This problem involves using Matlab to compute moving averages. Point out that a continuous-time version is assigned this week (not involving Matlab). Point out that the moving average has state (to point ahead to material covered later). Also, use this to explain how to define functions in Matlab.
  • Chapter 3, problem 3 (be sure to consider stuttering).
  • Review the Equal example (p. 71 of Sp 2000 reader), and show that no FSM model exists.
  • Chapter 3, problem 6 (construct an infinite state machine model for Equal).
  • If there is time, formulate an FSM for tic-tac-toe.

To student pages.