|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.