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},\ldots ,x_{0})$ and $y=(0,y_{n-1},\ldots ,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.