Show that the PCP is decidable over a unary alphabet ie over

Show that the PCP is decidable over a unary alphabet, i.e., over the alphabet ? = {1}

Show that the PCP is decidable over a unary alphabet, i.e., over the alphabet sigma = {1}. (The algorithm is indeed a very efficient one.)

Unary aplhabet is the aplhabet in which dominoes only differ in the number of 1s that

each has on the top and bottom.

Algorithm:

Let Set S=“Given a collection of dominoes

A) Even if one dominoe has the same number of 1s on top and bottom, then

is a match, so we have to accept it.

B)If all the dominoes have more 1’s on top than on bottom, there is no

way to a match, hence we have to reject it. In same way, if all the dominoes have

less 1’s on top than on bottom, then reject all.

C). Find one dominoe with more 1’s on top than on bottom (Let call it diff-

ference of FIRST 1s), and one dominoe with more 1s on bottom than on

top (Let call it diff-

ference of SECOND 1s). Choosing SECOND of the first dominoe and FIRST

of the second should make an equal number of 1s on both top and

bottom, and hence a match.