Turing’s World Ch8 Exercise 1

Exercise 1 (Dragonslayer) Imagine a knight on a journey through a land infested with dragons (D’s) and evil trolls (T’s), as well as some friendly civilians (F’s). He starts his journey with no weapons, but along the way he can find swords (S’s), used to slay dragons, and acquire spells (#’s), used to enchant the stupid trolls. He can carry at most one of each at any one time, and they are gone once he uses them. Luckily, people seem to have dropped a lot of swords and spells around the landscape.Design a one-way finite state machine that accepts a string if and only if the string represents a journey on which the knight survives. Thus, for example, it should accept FSFD#STFD but it should reject FSFD#STFDT, since the final troll gets the best of him.
Current State Symbol Read Action Next State
0 S MOVE RIGHT 1
0 # MOVE RIGHT 2
0 D MOVE RIGHT 4
0 T MOVE RIGHT 4
0 F MOVE RIGHT 0
1 # MOVE RIGHT 3
1 D MOVE RIGHT 0
1 T MOVE RIGHT 4
1 F MOVE RIGHT 1
2 S MOVE RIGHT 3
2 T MOVE RIGHT 0
2 D MOVE RIGHT 4
2 F MOVE RIGHT 2
3 D MOVE RIGHT 2
3 T MOVE RIGHT 1
3 F MOVE RIGHT 3
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: