12.3 THE POST CORRESPONDENCE PROBLEM
The undecidability of the halting problem has many consequences of practical interest, particularly in the area of context-free languages. But in many instances it is cumbersome to work with the halting problem directly, and it is convenient to establish some intermediate results that bridge the gap between the halting problem and other problems. These intermediate results follow from the undecidability of the halting problem (PC solution), but are more closely related to the problems we want to study and therefore make the arguments easier. One such intermediate result is the Post correspondence problem.
The Post correspondence problem can be stated as follows. Given two sequences of n strings on some alphabet ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
