POST'S CORRESPONDENCE PROBLEM

PCP: Given two sequences of strings {}\ e.g.

This instance has a solution if there is any sequence of integers , with

e.g. Solution is

e.g.

This instance does not have any solution.

Think about an algorithm which takes an instance of PCP and outputs solution sequence, if there is any; otherwise terminates with a 'No' answer.

Assume

Think also about time complexity.