The intersection of a DCG and a FSA

First note that the problem of calculating the intersection of a DCG and a FSA can be solved trivially by a generalization of the construction by [1]. However, if we use that method we will end up (typically) with an enormously large forest grammar that is not even guaranteed to contain solutions ¹. Therefore, we are interested in methods that only generate a small subset of this; e.g. if the intersection is empty we want an empty parse-forest grammar.

The straightforward approach is to generalize existing recognition algorithms. The same techniques that are used for calculating the intersection of a FSA and a CFG can be applied in the case of DCGs. In order to compute the intersection of a DCG and a FSA we assume that FSA are represented as before. DCGs are represented using the same notation we used for context-free grammars, but now of course the category symbols can be first-order terms of arbitrary complexity (note that without loss of generality we don't take into account DCGs having external actions defined in curly braces).

**Figure 2:** Instance of a PCP problem.
$\begin{figure} \setlength{\unitlength}{.8pt}\begin{picture} (400,100)(-100,0) \p... ...ox(0,0){$A_3$}} \put(260,40){\makebox(0,0){$B_3$}} \end{picture}\par\end{figure}$

**Figure 3:** Illustration of a solution for the PCP problem of figure 2.
$\begin{figure} \setlength{\unitlength}{.8pt}\begin{picture} (400,100)(0,0) % one... ...= 101111110}} \put(525,75){\makebox(0,0){= 101111110}} \end{picture}\end{figure}$

But if we use existing techniques for parsing DCGs, then we are also confronted with an undecidability problem: the recognition problem for DCGs is undecidable [11]. A fortiori the problem of deciding whether the intersection of a FSA and a DCG is empty or not is undecidable.

This undecidability result is usually circumvented by considering subsets of DCGs which can be recognized effectively. For example, we can restrict the attention to DCGs of which the context-free skeleton does not contain cycles. Recognition for such `off-line parsable' grammars is decidable [11].

Most existing constraint-based parsing algorithms will terminate for grammars that exhibit the property that for each string there is only a finite number of possible derivations. Note that off-line parsability is one possible way of ensuring that this is the case.

This observation is not very helpful in establishing insights concerning interesting subclasses of DCGs for which termination can be guaranteed (in the case of FSA input). The reason is that there are now two sources of recursion: in the DCG and in the FSA (cycles). As we saw earlier: even for CFG it holds that there can be an infinite number of analyses for a given FSA (but in the CFG this of course does not imply undecidability).