Next: What to do? Up: The intersection of a Previous: The intersection of a

Subsections

## Intersection of FSA and off-line parsable DCG is undecidable

I now 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. [5, 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 [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

vi1, vi2,..., vim = wi1, wi2,..., wim.

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

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.

#### Encoding of PCP.

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 a1...am, and the i -th member of B is b1...bn): r([a1...am| A], A,[b1...bn| B], B) [x].
2.
Furthermore, there is a rule r(A0, A, B0, B) r(A0, A1, B0, B1), r(A1, A, B1, 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. This FSA generates x*.
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 (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


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

Next: What to do? Up: The intersection of a Previous: The intersection of a
Noord G.J.M. van
1998-09-29