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 phrase-structure grammars
Marica D. Presi\'c and Slavisa B. Presi\'cMatematicki fakultet, Beograd, Yugoslavia
Abstract: 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.
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