Example: Domino D1 has string ``aa'' on top and string ``aaa'' on bottom; domino D2 has strings ``bba'' and ``b''; and domino D3 has strings ``a'' and ``abba''. Then the string of dominos D2, D2, D3, D1 spells out the same string ``bbabbaaaa'' on both top and bottom.
The Post correspondence problem is, surpringly, only semi-decidable. If there is an answer then, obviously, one can find it by exhaustive search; however, there is no algorithm that always terminates and that always answers correctly whether or not an instance of the problem has a solution. The problem can be characterized in terms of the following state space:
You may use an input file (or terminal input) of the following form:
First line: Maximum depth to search.
Second line: Number of dominos.
Remaining lines: 1 line per domino; each line contains the domino number and the two strings. You may assume a maximum of 20 characters per domino and a maximum of 20 dominos. You may assume that the input is correctly formatted and conforms to the maximums; you need not do error checking.
For instance, consider the following problem: 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''. The input for this problem might be
10 3 1 bb b 2 a aab 3 abbba bb
Part 1: The number of states generated at each successive level of the search space.
Part 2: The solution. This has one of the following three forms:
empty -----> D1 -----> D1,D1 -----> D1,D1,D1 -----> D1,D1,D1,D1 | bb bbbb | bbbbbb | bbbbbbbb | b bb | bbb | bbbb | | | | | |--> D1,D1,D1,D3 | | bbbbbbabbba | | bbbbb | | | |--> D1,D1,D3 Fails | bbbbabbba | bbbb | |--> D2 -----> D2,D2 Fails a | aa aab | aabaab | |--> D2,D3 -----> D2,D3,D2 -----> D2,D3,D2,D1 Succeeds aabbba aabbbaa aabbbaabb aabbb aabbbaab aabbbaabbThe output is therefore:
Level 0: 1 state Level 1: 2 state Level 2: 3 states Level 3: 3 states Level 4: 3 states Solution: D2,D3,D2,D1. aabbbaabb.At the last level, the count should be the number of states up to and including the solution state, but should not include states on the bottom level to the right of the solution state.
If the maximum depth of search were specified as 2 on the first line of the input file, then the output would be
Level 0: 1 state Level 1: 2 state Level 2: 3 states No solution was found within the limits of search.
Grading: 8 points for correctly running code. 2 points for well-written code. A programming assignment count equally with a problem set in computing the overall grade.