Discrete Mathematics

Class 13: State Machines


There is no Problem Set due this week. Problem Set 6 will be posted soon and due next Friday (October 20) at 6:29pm.

Exam 1 was returned in class today. Please read the solutions posted in collab: Exam 1 Comments. If you didn’t pick up Exam 1 in class today, you can get it at Dave’s office hours tomorrow, or before or after class on Thursday.

State Machines

A state machine is a binary relation (called a transition relation) on a set (both the domain and codomain are the same set). One state is designated as the start state.

$$M = (S, G: S \times S, q_0 \in S)$$

What does it mean if $G$ is total?


What does it mean if $G$ is not a function?


Parity Counter. Describe a state machine that determines if the number of steps is even.


Unbounded Counter. Describe a state machine that counts the number of steps.


How well do state machines model real computers? What kind of transition relation does the state machine modeling your computer have?

State Machine Execution

An execution of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a (possibly infinite) sequence of states, $(x_0, x_1, \cdots, x_n)$ where:

  1. $x_0 = q_0$ (it begins with the start state), and
  2. $\forall i \in {0, 1, \ldots, n - 1} \ldotp (xi, x{i + 1}) \in G$ (if $q$ and $r$ are consecutive states in the sequence, then there is an edge $q \rightarrow r$ in $G$)

A state $q$ is reachable if it appears in some execution. (That is, there is a sequence of transitions starting from $q_0$, following edges in $G$, that ends with $q$.)

$$ M_1 = (S = \mathbb{N}, G = {(x, y) | y = x^2 }, q_0 = 1) $$ $$ M_2 = (S = \mathbb{N}, G = {(x, y) | \exists k \in \mathbb{N} \ldotp y = kx }, q_0 = 1) $$

Which states are reachable for $M_1$ and $M_2$?