Let’s look at an example: suppose we wanted
a derivation of the
state
◊■■ in the system [STR]. Here’s a derivation which does the job:
1.
■■◊◊
initial state
2.
■■■◊◊
[R2]
■■◊
ø
3.
◊■■◊
[R1]
■■◊
4.
■■◊■■■◊
[R2]
◊■■ ø
5.
■■■■◊
[R2]
■■ ■■◊
6.
◊■■
[R1]
■■
The annotations on the right tell us how the state has been obtained –
which rule was used and how the string variables in the rule have been
instantiated. So, for example, state 2 was derived from state 1 (the
initial state) by applying [R2] to it and taking to be
■■◊ and to
be ø (empty), resulting in an
instantiation of the form
■■◊ (where
is
■■◊), namely ■■■■◊◊.
But note that we could have applied [R2] to the initial state in a
di
fferent way. We could have taken to be ■■ and to be ◊, resulting
in
■■■■◊. This means that [STR] is a
non-deterministic formal system.
A
system is deterministic if, for any given state, at
most one rule
applies to it and in only one way. If more than one rule applies to any
particular
state of the system, or if one rule applies to a particular
state of the
system in more than one way, then the system is
non-
deterministic.
Exercise 7.2
How many di
fferent ways can you apply [R2]
to the state
■■■■◊◊ and what would the output be in each case? What
about the states
■◊◊■◊◊ and ◊◊◊■■? What is the pattern?
You may have noticed that the result of applying [R2]
to the initial
state in the alternative way we discussed (taking to be
■■ rather
than
■■◊) is identical to state 5 in the derivation. This means that we
can actually get from the initial state to state 5 in the example in only
one step (rather than four).
It will often be the case that there will be more than one way of
deriving a given state. Often, we are interested
in finding the simplest
(i.e. shortest) derivation.
Do'stlaringiz bilan baham: