Abstract
We consider several language generating formalisms from the literature,
such as string-valued attribute grammars with only s-attributes,
parallel multiple context-free grammars, relational grammars and
top-down tree-to-string transducers, of which we have chosen the
OnlyS string-valued attribute grammars to be our vantage point. We
prove that OnlyS string-valued attribute grammars, parallel multiple
context-free grammars and relational grammars generate the same class
of languages, and we prove that every language accepted by an OnlyS
string-valued attribute grammar is the image of a top-down tree-to-string
transducer. The main result of this thesis is the proof of equivalence
of the special string-valued attribute grammars, the multiple context-free
grammar, the special relational grammar and the finite copying top-down
tree-to-string transducer. In order to prove these equivalences,
definitions of some of these formalisms have been slightly modified,
and normal forms have been (re)defined and proven
Users
Please
log in to take part in the discussion (add own reviews or comments).