For each problem listed below, give a complete problem defining the following.

1. State representation

2. Initial state

3. Goal state

4. Actions

5. Path cost a. You start with the sequence ABABAECCEC, or in general any sequence made from A, B, C, and E. you can transform this sequence using the following equalities: AC = E, AB = BC, BB = E, and Ex = x for any x. for example, ABBC can be transformed into AEC, and then AC, and then E. your goal is to produce the sequence E. b. You have to color the various regions of a planar map (for example, the map of the 48 contiguous states of the United States) using only four colors (Red, Blue, Yellow, and Green), in such a way that no two adjacent regions have the same color. 2. For the following tree, show the order of nodes visited for breadth-first search, iterative deepening search and uniform cost search. The start state is A and the goal node is L and the numbers next to the edges indicate the associated cost. (a) breadth-first search, (b) Iterative deepening search, (c) uniform cost search.

For the following tree, show the order of nodes visited for breadth-first search, iterative deepening search and uniform cost search. The start state is A and the goal node is G and the numbers next to the edges indicate the associated cost. Order of nodes visited in each of the following cases and state the cost of search: (a) breadth-first search,

(b) depth-first search,

(c) uniform cost search.