PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.) Vol. 56(70), pp. (1994) 

A constructive proof of equivalence of formalism od DCG's with the formalism of type 0 phrasestructure grammarsMarica D. Presi\'c and Slavisa B. Presi\'cMatematicki fakultet, Beograd, YugoslaviaAbstract: We present a proof that definite clause grammars (DCG's) are equivalent in their generative power to type 0 phrasestructure 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. Classification (MSC2000): 03B65 Full text of the article:
Electronic fulltext finalized on: 1 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts
