Here I show that the question whether the intersection of a FSA and
an off-line parsable DCG is empty is undecidable.
A yes-no problem is *undecidable* (cf.
[3, pp.178-179]) if there is no algorithm that
takes as its input an *instance* of the problem and determines whether
the answer to that instance is `yes' or `no'. An instance of a
problem consists of a particular choice of the *parameters* of
that problem.

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 [3][chapter 8.5].

An instance of PCP consists of two lists,
*A* = *v*_{1}...*v*_{k} and
*B* = *w*_{1}...*w*_{k} of strings over some alphabet . This instance
has *a solution* if there is any sequence of integers
*i*_{1}...*i*_{m}, 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
[3] 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.

- 1.
- For each
1
*i**k*(*k*the length of lists*A*and*B*) define a DCG rule (the*i*-*th*member of*A*is*a*_{1}...*a*_{m}, and the*i*-th member of*B*is*b*_{1}...*b*_{n}):*r*([*a*_{1}...*a*_{m}|*A*],*A*,[*b*_{1}...*b*_{n}|*B*],*B*) [*x*]. - 2.
- Furthermore, there is a rule
*r*(*A*_{0},*A*,*B*_{0},*B*)*r*(*A*_{0},*A*_{1},*B*_{0},*B*_{1}),*r*(*A*_{1},*A*,*B*_{1},*B*). - 3.
- Furthermore, there is a rule
*s**r*(*X*,[ ],*X*,[ ]). Also,*s*is the start category of the DCG. - 4.
- Finally, the FSA consists of a single state
*q*which is both the start state and the final state, and a single transition (*q*,*x*) =*q*.

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 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:

s --> r(X,[],X,[]). r(A0,A,B0,B) --> r(A0,A1,B0,B1), r(A1,A, B1,B ). r([1|A],A,[1,1,1|B],B) --> [x]. r([1,0,1,1,1|A],A,[1,0|B],B) --> [x]. r([1,0|A],A,[0|B],B) --> [x].

1998-09-29