a. Design a FSA that will recognize sentences such as The dog that chased the cat that ate the mouse lived in the house that Jack built. Namely, the sentences should look like The ANIMAL1 that VERBED1 the ANIMAL2 that VERBED2 the ANIMAL3 VERBED3 in the house that Jack built., where ANIMALn is an animal and VERBEDn is a past-tense verb, 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 two special transitions, one that tests whether a word represents an animal, and one that tests whether a word is a verb.

b. Design a FSA that will recognize sentences such as The mouse the cat the dog chased ate lived in the house that Jack built., namely The ANIMAL1 the ANIMAL2 the ANIMAL3 VERBED3 VERBED2 VERBED1 in the house that Jack built. Assume that n 3 and that you have the same special transitions available.

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