Artificial Intelligence Programming Assignment 2 Assigned: Oct. 27 Due: Nov. 17 The Post correspondence problem, as described in class, has the following form: You are given a collection of dominos. Each domino has a string of characters on top and another string on the bottom. You can make as many copies of the dominos as you need. The problem is to place the dominos side by side so that the combination of the strings on the top is the same as the combination of the strings on the bottom. For example, suppose domino D1 has string ``bb" on top and string ``b'' on bottom; domino D2 has strings ``a'' and ``aab'' and domino D3 has strings ``abbba'' and ``bb''. Then the ordering D2, D3, D2, D1 spells out the string ``aabbbaabb'' both on the top and on the bottom. The following non-deterministic algorithm finds a solution to the Post correspondence problem if one exists: procedure post(S : set of dominos) return list of dominos; L := empty list repeat choose a domino D in S; add D to the beginning of L; if the string on the bottom is not a tail of the string on top and the string on top is not a tail of the string on the bottom then fail endif until the string on the bottom equals the string on the top return L The algorithm does not terminate if the problem has no solution. However, there is no algorithm that always finds a solution if one exists and always terminates if none exists (the problem is semi-decidable.) In other words, there is a search through a space of the following structure: > A state is a string on top and a string on bottom, such that one is a tail of the other. > An operator on string S takes some domino D and attaches the top of D to the front of the top of S and the bottom of D to the front of the bottom of S. > The start state is has the empty string on top and bottom > A goal state is one where the top is equal to the bottom and non-empty. In the above algorithm, we build the list from back to front rather than from front to back because that is more natural and efficient in both Prolog. Implement the above procedure in Prolog using an iterative deepening search. Show the results of running your procedure on the above example, and on the following example: D1 = bb/b D2 = a/baa D3 = abbba/bb D4 = bbb/ba