316 !!O! Theory ofComputer Science
Solution
We have to determine whether or not there exists a sequence of substrings of
x such that the string formed by this sequence and the string formed by the
sequence of corresponding substrings of yare identical. The required sequence
is given by i 1 = 2, i 2 = 1, i 3 = 1, i 4 = 3, i.e. (2, 1, 1,3), and m = 4. The
corresponding strings are
=
Thus the PCP has a solution.
EXAMPLE 10.2
Y2
Yl
Yl
Y3
Prove that PCP with two lists x = (01, 1, 1), Y = (01
2 , 10, 11) has no solution.
Solution
For each substring Xi E X and Yi E )', we have IXi I < IYi I for all i. Hence
the string generated by a sequence of substrings of X is shorter than the string
generated by the sequence of corresponding substrings of y. Therefore, the PCP
has no solution.
Note: If the first substring used in PCP is always Xl and Yb then the PCP
is known as the Modified Post Correspondence Problem.
EXAMPLE 10.3
Explain how a Post Correspondence Problem can be treated as a game of
dominoes.
Solution
The PCP may be thought of as a game of dominoes in the following way: Let
each domino contain some Xi in the upper-half, and the corresponding
substring of Y in the lower-half. A typical domino is shown as
o upper-half
~ lower-half
The PCP is equivalent to placing the dominoes one after another as a
sequence (of course repetitions are allowed). To win the game, the same string
should appear in the upper-half and in the lower-half. So winning the game
is equivalent to a solution of the PCP.
I