Re: Regular Tree Grammar vs. Context-Free Grammar

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)
:-)

--
Hans Aberg
.

Relevant Pages

  • Re: Regular Tree Grammar vs. Context-Free Grammar
    ... the relationship between regular tree grammars and CFGs? ... do the languages accepted by CFGs include the languages ... 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 ...
    (comp.theory)
  • Re: Regular Tree Grammar vs. Context-Free Grammar
    ... the relationship between regular tree grammars and CFGs? ... 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 ...
    (comp.theory)
  • Re: Regular Tree Grammar vs. Context-Free Grammar
    ... Regular Word Grammar < Regular Tree Grammar < Context-Free Grammar ... because every regular tree grammar can be simulated by a CFG using "matching parenthesis". ... And you might just as well augment the terminal set by a disjoint union of ... formally distinct copy. ...
    (comp.theory)