Chapter 6

Modeling Computation
Learning Outcome
Students should be able to:

Analyze problems and modeling the solutions

Modeling Computation
Computers can perform many tasks. Given a task,
two questions arise:
Can it be carried out using a computer?
How can the task be carried out?
What is an algorithm?
A description of a computational procedure.
How can we model the computer itself, and what it
is doing when it carries out an algorithm?
How to model the abstract process of
computation?
 Computers as Transition Functions
A computer (or really any physical system) can be
modeled as having, at any given time, a specific state
sS from some (finite or infinite) state space S.

At any time, the computer receives an input symbol

iI and produces an output symbol oO.
Where I and O are sets of symbols.
 Each “symbol” can encode an arbitrary amount of data.

A computer can then be modeled as simply being a

transition function T:S×I → S×O.
Given the old state, and the input, this tells us what the
computer’s new state and its output will be a moment later.
Finite State Machine (FSM)
A mathematical models of computation used to
design computer programs
Consists of a set of states, including a starting state, an
input alphabet, and a transition function that assigns a
next state to every pair of a state and an input.
Some FSMs produce an output symbol for each
transition
FSM: Applications
FSM can be used to model many kinds of
machines, including vending machines, delay
machines, binary adders, and language recognizers

used in a variety of applications such as

 spellchecking programs;
 grammar checking;

 indexing and searching large text files;

 speech/language recognition;
 network protocols
Types of FSM
FSM with Output
Mealy Machine: Output determined by state and input
Moore Machine: Output determined by state alone
FSM with No Output
Also known as finite-state automata
There are two types of finite-state automata
 Deterministic: Each state-input pair dictates a unique transition
into another state
 Non-deterministic: Each state-input pair can lead to several
possible states
Vending Machine Example
Suppose a certain vending machine
accepts nickels, dimes, and quarters.
If >30¢ is deposited, change is
immediately returned.
When there is 30¢ deposited,
if the “coke” button is pressed
Ignore any other
the machine drops a coke. buttons, bills,
It can then accept a new payment. out of change,
etc.
Transition Function Table
Input symbol set:
I = {nickel, dime, quarter, button}
Output symbol set:
O = {, 5¢, 10¢, 15¢, 20¢, 25¢, coke}
State set: Representing how much money has been taken.
S = {0, 5, 10, 15, 20, 25, 30}

Old New Old New

state Input state Output state Input state Output
0 n 5  10 n 15 
0 d 10  10 d 20 
0 q 25  10 q 30 5¢
0 b 0  10 b 10 
5 n 10  15 n 20 
5 d 15  15 d 25 
5 q 30  15 q 30 10¢
5 b 5  15 b 15 
Transition Function Table cont.
Old New Old New
state Input state Output state Input state Output
20 n 25  30 n 30 5¢
20 d 30  30 d 30 10¢
20 q 30 15¢ 30 q 30 25¢
20 b 20  30 b 0 coke
25 n 30 
25 d 30 5¢
25 q 30 20¢
25 b 25 
Another Format: State Table
Input Symbol Each pair shows:
new state, output symbol
Old n d q b
state
0 5, 10, 25, 0,
5 10, 15, 30, 5,
10 15, 20, 30,5¢ 10,
15 20, 25, 30,10¢ 15,
20 25, 30, 30,15¢ 20,
25 30, 30,5¢ 30,20¢ 25,
30 30,5¢ 30,10¢ 30,25¢ 0,coke
Directed-Graph State Diagram
As you can see, these can get kind of busy.
q,5¢ d,5¢
q q
d d q,20¢
d n
n n n n n
0 5 10 15 20 25 30

b b b b b b
n,5¢
d,10¢
q,15¢ q,25¢
b,coke

q,10¢
Formalizing FSMs
the output function separated from the transition function,
and with the various sets added in, along with an initial
state.
A finite-state machine M=(S, I, O, f, g, s )
0
 S is the state set
 I is the alphabet (vocabulary) of input symbols
 O is the alphabet (vocabulary) of output symbols
 f is the state transition function
 g is the output function
 s is the initial state
0
Our transition function from before is T = (f,g).
Finite State Machine (FSM)
Start a Example of a simple FSM
p q p = start state
a = transition
q = accept state

FSM consists of states, inputs and outputs.

The number of states is fixed
When an input is executed, the state is changed and an output is
possibly produced.
A double circle signifies the accepting state.
Not all FSMs will have an accepting state and it is possible they
could run forever.
FSM can be with or without outputs
applied in engineering, biology, linguistics and other sciences due
to their ability to recognise sequences.
Example: FSM with no outputs

FSM accepting binary input

 Also called as finite state automata 

 they do not produce output, but they do have a set of final states
 It starts in state S1, an input of 1 will keep it in state one
 An input of 0 will move it to state S2.
 Once in S2 an input of 1 will keep it there, and an input of 0 will switch
it back to S1.
 The following inputs are valid:

110011001
001110011

(Note: The singular of automata is automaton.)

FSM with no output

Which of these inputs are valid:

A. aacdb
B. ababacdaaac
C. abcdb
D. acda
E. acdbdb A. aacdb (CORRECT)
B. ababacdaaac(CORRECT)
C. abcdb (ERROR no input that accepts b then c)
D. acda (ERROR S1 is not a accepting state)
E. acdbdb (CORRECT)
FSM with no output

Which of these inputs are valid:

A. 987654321+994-0
B. 5-5+2*4
C. 9+8+7+6+5+4+3+2+1
D. 0+1+2+1+
E. 99+88-77
A. 987654321+994-0 (CORRECT)
B. 5-5+2*4 (ERROR no input *)
C. 9+8+7+6+5+4+3+2+1 (CORRECT)
D. 0+1+2+1+ (ERROR S3 is not a accepting state)
E. 99+88-77 (CORRECT)
Designing Finite-state Automata

 Construct a finite-state automaton that recognizes a given set of strings

by carefully adding states and transitions and determining which of
these states should be final states.
Construct deterministic finite-state automata that recognize each of these
languages.
(a) the set of bit strings that begin with two 0s
(b) the set of bit strings that contain two consecutive 0s
(c) the set of bit strings that do not contain two consecutive 0s
(d) the set of bit strings that end with two 0s
(e) the set of bit strings that contain at least two 0s
Deterministic FSM
Nondeterministic FSM

FSM - in which there may be several possible next

states for each pair of input value and state
Nondeterministic FSM
Draw a state diagram based on the state transition table below:
Example: Finite State with Output
 The state table describes a finite-state machine with S = {s0, s1, s2, s3},
I = {0, 1}, and O = {0, 1}.
 The transition function f are displayed in the first two columns, and the
values of the output function g are displayed in the last two columns.
 Draw a finite state machine diagram from the table.
Example: Finite State With Output
1. Construct a state transition table from the FSM diagram
2. Find the output string generated by the finite-state machine if
the input string is 101011
FSM
Draw a finite state automata that will accept the word
Banana whilst using only 3 states

Answer:
FSM
Draw a finite state automata that will accept the words:
Tim
Grit
Grrrrrim

Answer:
Mealy Machine: FSM with Output
 Mealy Machine - an FSM with outputs
 The output values dependant on the state and the input values.
 Mealy Machine outputs a value for each input.

What do the following inputs output:

1. 50
2. 20,10,20
3. 10,10,10,20

 What does this machine do, what do the outputs tell you?

1. 0
Answer:
2. 30,20,0
3. 40,30,20,0
This machine could be used to track the money going into a vending machine, letting you know how much you have left
to pay on a 50p chocolate bar
Class Activity 1
Construct the state tables for the finite-state machines
from the state diagrams below:
Class Activity 2
1. Construct a finite-state machine that models an old-fashioned soda
machine that accepts nickels, dimes, and quarters. The soda machine
accepts change until 35 cents has been put in. It gives change back for any
amount greater than 35 cents. Then the customer can push buttons to
receive either a cola, a root beer, or a ginger ale.

2. Construct a finite-state machine for a toll machine that opens a gate after
25 cents, in nickels, dimes, or quarters, has been deposited. No change is
given for overpayment, and no credit is given to the next driver when more
than 25 cents has been deposited.

3. Construct a finite-state machine that determines whether the word

computer has been read as the last eight characters in the input read so far,
where the input can be any string of English letters.