Complex FSAs

a) Design a FSA that will recognize sentences such as Theres a feather on the water on the leaf on the lake in the forest in the valley. Namely, the sentences should look like Theres an THING1 on/in the THING2 on/in the THING3 . . . on/in the THINGn, where THINGn is a thing, and where the maximum n can be arbitrarily large. Assume that words are fed to the FSA one at a time (not a character at a time), and your FSA may include one special transition that tests whether a word represents a noun or not.

b) Design an FSA that will recognize sentences such as The police the man the women killed arrested lived in the small apartment which the government built, namely AC- TOR1 ACTOR2 ACTOR3 . . . VERBED3 VERBED2 VERBED1 lived in PLACE1 which the government built. Assume that n <= 3 and that you have two special transitions available, one that tests whether a word represents an animal, and the other that tests whether a word is a verb.

c) For part (b), would it be possible to design an FSA that would work to arbitrary depth n? Why or why not? What is different between the FSA in part (a) and (b)?