Re: Regular Tree Grammar vs. Context-Free Grammar

Eric Wohlstadter <wohlstad@xxxxxxxxx> writes:

Hello,
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.

--
Ben.
.

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? ... of a CFG are sequences, but the way the productions of an RTG are ... And you might just as well augment the terminal set by a disjoint union of ... formally distinct copy. ...
    (comp.theory)
  • Re: Equivalence of two CFGs
    ... Lash Rambo wrote: ... CFG 1: ... it as an abstract set of productions, ...
    (comp.theory)