Class 13: State Machines

### Schedule

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:

- $x_0 = q_0$ (it begins with the start state), and
- $\forall i \in {0, 1, \ldots, n - 1} \ldotp (x
*i, 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$?

#