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

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

 		 

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\'c

Matematicki 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
© 2001 ELibM for the EMIS Electronic Edition