Hardware Reference
In-Depth Information
strategies by which a boatman can take the three items from one shore to the other,
and repeat it forever.
1. Design the co-Buchi specification automaton.
Solution.
The co-Buchi specification has one input,
out
, and has three states,
a
,
b
,and
c
.
The initial state is
, which is a sink (so
the specification is a co-looping automaton). A transition is made from
a
; the stable region consists only of state
c
a
to
c
if
out = done
, from
a
to
b
if
out = notOK
and from
a
to
a
if
out = OK
.
Also state
is a sink.
The specification
spec.aut
follows (
accepting
here refers to the co-
Buchi acceptance conditions):
b
# 00 = null, 10 = OK, 01 = notOK, 11 = done
.i 2
.o 0
.s 3
.p 5
.ilb out_0 out_1
.ob
.accepting c
-0aa
01ab
11ac
--bb
--cc
.e
2. Design the fixed component automaton
(see Problem 17.2).
3. Compute the most general solution automaton.
4. Minimize the most general solution automaton.
5. To find a particular implementation, the most general solution automaton is split
into two automata: the acceptance automaton and the path automaton. From
the minimized most general solution automaton, obtain the acceptance and path
automata.
6. Make progressive the acceptance automaton.
7. In the path automaton there are cycles and a state that cannot reach the target state
f
F
. Pre-process the path automaton to remove cycles consisting only of essential
transitions and backward transition edges.
8. Extract a particular solution from the path automaton.
18.2.
Compare the specifications of the Wolf-Goat-Cabbage game as described in
Problem 17.2 as a regular game, and in Problem
18.2
as an
-regular game.
Notice that the way to model a game that we described in Chap. 17 allows the
possibility of meaningless solutions, e.g., in the Wolf-Goat-Cabbage example never
getting all three on the opposite shore, i.e., essentially shuffling items back and forth
forever; another example of meaningless solution might be that the system does not
progress from the initial state. So it may be that the language of the solution of a
!
Search WWH ::
Custom Search