I use Post's Correspondence Problem (PCP) as a well-known undecidable problem. I show that if the above mentioned intersection problem were decidable, then we could solve the PCP too. The following definition and example of a PCP are taken from [5][chapter 8.5].
An instance of PCP consists of two lists,
A = v1...vk and
B = w1...wk of strings over some alphabet . This instance
has a solution if there is any sequence of integers
i1...im, with m
1, such that
Clearly there are PCP's that do not have a solution. Assume again that
= {0, 1}. Furthermore let
A =
1
and
B =
0
. Clearly this PCP does not have a solution. In
general, however, the problem whether some PCP has a solution or not
is not decidable. This result is proved by
[5] by showing that the halting problem for
Turing Machines can be encoded as an instance of Post's Correspondence
Problem.
First I give a simple algorithm to encode any instance of a PCP as a pair, consisting of a FSA and an off-line parsable DCG, in such a way that the question whether there is a solution to this PCP is equivalent to the question whether the intersection of this FSA and DCG is empty.
The underlying idea of the algorithm is really very simple. For each pair of strings from the lists A and B there will be one lexical entry (deriving the terminal x) where these strings are represented by a difference-list encoding. Furthermore there is a general combination rule that simply concatenates A-strings and concatenates B-strings. Finally the rule for s states that in order to construct a succesful top category the A and B lists must match.
The resulting DCG, FSA pair for the example PCP is given in as:
trans(q0,x,q0). start(q0). final(q0). % FSA top(s). % start symbol DCG rule(s,[-r(X,[],X,[])]). % require A's and B's match rule(r(A0,A,B0,B),[-r(A0,A1,B0,B1), % combine two sequences of -r(A1,A,B1,B)]). % blocks rule(r([1|A], A,[1,1,1|B],B),[+x]). % block A1/B1 rule(r([1,0,1,1,1|A],A,[1,0|B], B),[+x]). % block A2/B2 rule(r([1,0|A], A,[0|B], B),[+x]). % block A3/B3