Intersection of FSA and off-line parsable DCG is undecidable

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₁...v_k and B = w₁...w_k of strings over some alphabet $\Sigma$. This instance has a solution if there is any sequence of integers i₁...i_m, with m $\geq$ 1, such that

v_i1, v_i2,..., v_im = w_i1, w_i2,..., w_im.

The sequence i₁,..., i_m is a solution to this instance of PCP. As an example, assume that $\Sigma$ = {0, 1}. Furthermore, let A = $\langle$1, 10111, 10$\rangle$ and B = $\langle$111, 10, 0$\rangle$. A solution to this instance of PCP is the sequence 2,1,1,3 (obtaining the sequence 101111110). For an illustration, cf. figure 1.

Figure 1: Illustration of a solution of a PCP problem.

Clearly there are PCP's that do not have a solution. Assume again that $\Sigma$ = {0, 1}. Furthermore let A = $\langle$1$\rangle$ and B = $\langle$0$\rangle$. 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.

Encoding of PCP.

1.

For each 1 $\leq$ i $\leq$ k (k the length of lists A and B) define a DCG rule (the i - th member of A is a₁...a_m, and the i -th member of B is b₁...b_n): r([a₁...a_m| A], A,[b₁...b_n| B], B) $\rightarrow$ [x].

2.

Furthermore, there is a rule r(A₀, A, B₀, B) $\rightarrow$ r(A₀, A₁, B₀, B₁), r(A₁, A, B₁, B).

3.

Furthermore, there is a rule s $\rightarrow$ 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 $\delta$(q, x) = q.

Observe that the DCG is off-line parsable.

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].

Proposition

The question whether the intersection of a FSA and an off-line parsable DCG is empty is undecidable.

Proof.

Suppose the problem was decidable. In that case there would exist an algorithm for solving the problem. This algorithm could then be used to solve the PCP, because a PCP $\pi$ has a solution if and only if its encoding given above as a FSA and an off-line parsable DCG is not empty. The PCP problem however is known to be undecidable. Hence the intersection question is undecidable too.