Re: Regular Tree Grammar vs. Context-Free Grammar

haberg@xxxxxxxxxx (Hans Aberg) writes:

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

I am a little unsure about the value of saying anything. The trouble
is that the equivalence is not very formal. The Languages of RTGs are sets
of trees and those of CFGs are sets of strings.

All one can say, formally, is that one can construct a CFG whose
language can be mapped to that of the RTG with a rather trivial 1-to-1
function. There is no CFG that describes the same language as an RTG.

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

Indeed. But one also has to add the tedious detail that one is
building a CFG whose language is {flatten(t) | t ∈ L_r} with

flatten: T_Σ ↦ Σ'*
flatten(s) = s
flatten(s(t₁, … t_n)) = s '(' flatten(t₁) ',' … flatten(t_n) ')'

so the result is not equivalent except to computer scientist who can
see that flatten (and, importantly, its inverse) are trivial to compute.

--
Ben.
.

Relevant Pages

  • Re: Regular Tree Grammar vs. Context-Free Grammar
    ... If there is an isomorphism from tree structures to word structures, then we should be able to evaluate the "power" of regular tree grammars relative to the classical Chomsky hierarchy of grammars. ... do the languages accepted by CFGs include the languages ... 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
    ... The Languages of RTGs are sets ... of trees and those of CFGs are sets of strings. ... There is no CFG that describes the same language as an RTG. ...
    (comp.theory)
  • Re: Equivalence of two CFGs
    ... CFG 1: ... Re-write CFG1 to use a new production B' -> A and then fiddle with the C ... until you get CFG2! ...
    (comp.theory)
  • Re: Equivalence of two CFGs
    ... Ben Bacarisse wrote in ... CFG 1: ... then fiddle with the C until you get CFG2! ...
    (comp.theory)