Which one of the following instances of the Post Correspondence Problem has a viable sequence?
The instance {(ab, abb), (ba, aaa), (aa, a)} has a matching sequence. Taking tiles 1, 2, 3, 3 gives ab·ba·aa·aa = abbaaaaa on top and abb·aaa·a·a = abbaaaaa on the bottom.
Choose your answer
Which one of the following instances of the Post Correspondence Problem has a viable sequence?
Answer and explanation
Correct answer C
The instance {(ab, abb), (ba, aaa), (aa, a)} has a matching sequence. Taking tiles 1, 2, 3, 3 gives ab·ba·aa·aa = abbaaaaa on top and abb·aaa·a·a = abbaaaaa on the bottom.
Practice for these exams
-
Karnataka SET (KSET)