Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Class 13: State Machines


Schedule

Exam 1 Solutions are now posted.

Drop Date is today. If you have any concerns about whether you should stay in the class, please talk to me after class today.

There is no problem set due this week! Problem Set 6 (will be posted later this week) is due 21 October (Friday) at 6:29pm.

Exam 1 was returned during class today. (Exam grades will eventually make it into collab, but haven’t yet. When they do, please confirm that the score on your exam matches what is recorded in collab, and that PS1-5 are all recorded correctly.)

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?

Invariant Principle

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$?

#

A preserved invariant of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state $q$, and $q \rightarrow r \in G$, then $P®$ is true.

Invariant Principle. If a preserved invariant of a state machine is true for the start state, it is true for all reachable states.

To show $P(q)$ for machine $M = (S, G \subseteq S \times S, q_0 \in S)$ all $q \in S$, show:

  1. Base case: $P(\fillin)$
  2. $\forall s \in S \ldotp \fillin \implies \fillin$

Show the invariant principle holds using the principle of induction (hint: induction is on the number of steps).

#