Question 1: Language Generation We would like to design a simple language generation system which can generate sensible and grammatically correct sentences of English of up to length six. 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 on the mat sat the cat sat on the mat The system also incurs a cost for generating each word, equal to the number of consonants the word contains. a) Formulate the sentence generation process as a (constructive) search problem, stating each of the parts of the search problem as shown in class. How large is the state space of this problem? Assume that sentences must contain at least one and no more than six words. b) Draw the search graph of this problem. If the graph turns out to be too large, draw a portion of it and indicate how the graph will be extended using some prose and notation. How is it different from the search tree? c) Trace the run of the search process using the following algorithms for up to 10 steps of the algorithm. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer to generate the word that comes first alphabetically. i. ii. Breadth first search Uniform cost search Depth first search Iterative deepening iii. iv. d) Describe a scheme that uses local search for this problem, such that given enough running time, the algorithm would find a goal state. Be sure to state each of the parts of the local search algorithm as shown in class. Question 1: Language Generation We would like to design a simple language generation system which can generate sensible and grammatically correct sentences of English of up to length six. 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 on the mat sat the cat sat on the mat The system also incurs a cost for generating each word, equal to the number of consonants the word contains. a) Formulate the sentence generation process as a (constructive) search problem, stating each of the parts of the search problem as shown in class. How large is the state space of this problem? Assume that sentences must contain at least one and no more than six words. b) Draw the search graph of this problem. If the graph turns out to be too large, draw a portion of it and indicate how the graph will be extended using some prose and notation. How is it different from the search tree? c) Trace the run of the search process using the following algorithms for up to 10 steps of the algorithm. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer to generate the word that comes first alphabetically. i. ii. Breadth first search Uniform cost search Depth first search Iterative deepening iii. iv. d) Describe a scheme that uses local search for this problem, such that given enough running time, the algorithm would find a goal state. Be sure to state each of the parts of the local search algorithm as shown in class