Re: Regular Tree Grammar vs. Context-Free Grammar

Thanks for the replies.

Just to be clear then: There is a hierarchy of inclusion:

Regular Word Grammar < Regular Tree Grammar < Context-Free Grammar

because every regular tree grammar can be simulated by a CFG using "matching parenthesis". Furthermore, regular tree grammars are a proper subset of CFGs. That is, there are some CFGs which cannot be represented using a regular tree grammar.

Is this correct?

Eric

Hans Aberg wrote:
In article <87mz5zdru4.fsf@xxxxxxxxx>, Ben Bacarisse
<ben.usenet@xxxxxxxxx> wrote:

I am wondering if anyone can help me with information about
the relationship between regular tree grammars and CFGs? In particular
do the languages accepted by CFGs include (subsume) the languages
accepted by regular tree grammars?
The right hand sides of the productions of an RTG are trees and those
of a CFG are sequences, but the way the productions of an RTG are
written gives you a CFG if you just turn the meta-notation into
notation! Construct a CFG whose terminal alphabet is augmented with
three symbols: "{", ";" and "}" and turn each RTG production of the
form:

A -> f(X,Y)

into:

A -> f { X ; Y }

and so on. I've changed the brackets and separator to make the
transformation clearer, but there is no need to.

Perhaps you might add this to:
http://en.wikipedia.org/wiki/Regular_tree_grammar
And you might just as well augment the terminal set by a disjoint union of
the set {'(', ',', ')'}, a way to say that if these already exist, add a
formally distinct copy. Use indices to make a distinction at need. Then
A -> f(X,Y)
is replaced by
A -> f '(' X ',' Y ')'
which by "abuse of notation" may be written
A -> f(X,Y)
:-)

.