Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

Exercise 7.3
Give the shortest derivation in [STR] of the state 
◊■■.
 
63

---

You might wonder – given the indeterminacy of [STR] and the plu-
rality of derivations – whether there is, in general, an e
ffective proce-
dure for finding derivations in a formal system. This turns out to be a
very important question for the classical Artificial Intelligence
research tradition and it will be our focus when beginning Chapter 11.
For the moment, a couple of informal heuristics will serve to guide
you through the following exercises. Firstly, work backwards from the
solution. Examine the state you want to derive and determine whether
it could have been the output of any rule. If not, no need to continue;
if so, you will have a guide as to which input(s) could have delivered
that output. Try and get back to the initial state by working back-
wards through rules this way.
Secondly, aim for your goal. If you have a choice of rule applications
to a state which is longer than your goal state and one choice results in
a shorter output, it is likely (but not guaranteed) to be a good way to go.
Exercise 7.4
(a) Augment the system [STR] with the following rule:
[R3]
■◊ → ■◊
and give properly annotated derivations for the states:
1.
◊■■ 4.
◊◊◊■
2.
◊
5.
◊■■◊■■■◊
3.
◊◊■◊ 6.
◊◊◊■◊◊
(b) Can you generate a state without a 
◊? Explain your
reasoning.
7.5 GENERATION TREES
The answer to Exercise 7.4(b) brings out an important feature of the
system [STR] – that it has no terminal states.
We will call a state terminal if it is a generated state of the system
to which no rules apply. So, while 
■■ is a state of [STR] to which no
rules apply, it is not a terminal state since it is not a generated state.
All generated states of [STR] are ipso facto the output of a rule
and, hence, must contain a 
◊. Since [R2] applies to any state which
contains a 
◊ in it anywhere, there are no generated states to which no
rules apply. Hence, there are no terminal states of [STR].
Consider the specification below for the formal system [BIN]. Does
this system have any terminal states?
64
  

---

[BIN]
[S1]
ø is a state
[S2]
If  is a state then so is 1, 0 and 
[S3]
initial state is: 
[R1]
  

→  1 
 /  0 
 /    

The single rule of this system has a choice of three possible outputs –
the slash ‘/’ represents ‘or’. Read informally, it says that any  in a
state can be rewritten as a 1, or a 0, or as two s.
Given the initial state, the rule allows for the derivation of all and
only the finite strings of the symbols 1, 0 and . In other words, there
are no states of the system which are not generated. But are there any
terminal states?
Consider the three ways in which we can apply the rule to the initial
state. The resultant output states will be 1, 0 and  respectively. The
first two of these do not contain the symbol . As the only rule in the
system applies only to states which do contain at least one occurrence
of the symbol , the states 1 and 0 are terminal states.
In fact, a little reflection serves to show that the terminal states of
[BIN] will be all and only the finite strings of the symbols 1 and/or 0.
In other words, all and only the finite strings of binary (e.g. 1001011)
are terminal states of [BIN]. So any finite string of binary has a
derivation in [BIN].
This is clearer if we draw up a generation tree as shown in Figure 7.3.
Turn the diagram upside down and it becomes a little clearer as to
why these are called tree structures. The state at the top is the root node.
 
65