0. We would like to design a simple language generation system which can generate sensible and grammatically correct sentences of English of up to 6 words long. The system is able to generate these five words: the, cat, sat, on, mat.

   Thus, the sentences that we would want the system to generate are (we ignore capitalization and punctuation issues):

   the cat sat the cat sat on the mat. The system also incurs a cost for generating each word, equal to the number of letters the word contains.

1. Draw the search tree down to a depth of 2 (i.e., the tree has 3 levels in total, including the root.)

2. Trace the run of the search process using the following algorithms for up to 10 search steps. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer to generate the word that comes first alphabetically.

   1. Breadth first search

   2. Uniform cost search

   3. Depth first search

   4. Iterative deepening