1. Question 1 For this question, let us characterize the state space as follows: A state is sequence of dominocs where either the top string is a prefix of the bottom string or the bottom string is a prefix of top string. For example, {D3, D2} - blou is a valid state because "bba" is a prefix of "bbac", while {D1, D4} is not a valid state. The only we can take is to add a domino from the current The start state is an empty sequence of dominoes. A goal state is any sequence of dominoes where the top and bottom strings are equal. (a) Solve the example instance of the Post Correspondence given in the introduction using BFS search. Show the state space that is generated. When taking an action, test adding the dominoes in numerical order i.e. try D1 first, then D2 and so on). (b) Solve the example instance of the Post Correspondence given in the introduction using DFS search. Show the state space that is generated. (c) Explain that if the order we tested adding dominoes was different (not numerical order), DFS will not find a solution. Show the state space until at least depth 4 for the DFS search if the order the dominoes was tested in was inverse numerical order. 1. Question 1 For this question, let us characterize the state space as follows: A state is sequence of dominocs where either the top string is a prefix of the bottom string or the bottom string is a prefix of top string. For example, {D3, D2} - blou is a valid state because "bba" is a prefix of "bbac", while {D1, D4} is not a valid state. The only we can take is to add a domino from the current The start state is an empty sequence of dominoes. A goal state is any sequence of dominoes where the top and bottom strings are equal. (a) Solve the example instance of the Post Correspondence given in the introduction using BFS search. Show the state space that is generated. When taking an action, test adding the dominoes in numerical order i.e. try D1 first, then D2 and so on). (b) Solve the example instance of the Post Correspondence given in the introduction using DFS search. Show the state space that is generated. (c) Explain that if the order we tested adding dominoes was different (not numerical order), DFS will not find a solution. Show the state space until at least depth 4 for the DFS search if the order the dominoes was tested in was inverse numerical order