CSCE 222 Lecture 28

« previous | Wednesday, April 13, 2011 | next »

Finite State Machines

A finite state machine is defined by a six-tuple: $M=(S,I,O,f,g,s_0)$

• S — set of states
• I — input alphabet
• O — output alphabet
• f — transition function (what is the next state given the current state and input)
• g — output function (what kind of output should I produce?)
• s₀ — start state

Example

$M=(\{s_0,s_1\},x,y,f,g,s_0)$

Input: binary string of length $n$, $x=(0,x_{n-1},\dots ,x_0)$ and $y=(0,y_{n-1},\dots ,y_0)$

Output: Computes the sum of two integers $x$ and $y$. Add $x_0$ and $y_0$ producing a sum $z_0=x_0\oplus y_0$ and a carrier $c_0=x_0{y}_0$. Then $x_1$ and $y_1$ are added to the carrier bit yielding $z_1=x_1\oplus y_1\oplus c_0$ and another carrier $c_1=x_1{y}_1$. etc.