A Constructive Proof of Equivalence of Formalism od Dcg's With the Formalism of Type 0 Phrase-structure Grammars


Marica_D. Prešić, Slaviša_B. Prešić


We present a proof that definite clause grammars (DCG's) are equivalent in their generative power to type 0 phrase-structure grammars. The proof is constructive and it actually describes an algorithm for transferring from a language description by type 0 grammar to DCG characterization. The proof has been inspired by the proof given in [MA93] but our approach is considerably simpler and the constructed DCG grammar is much more efficient. The paper also suggests how computer implementation of the algorithm can be developed.