Re: Regular Tree Grammar vs. Context-Free Grammar

Eric Wohlstadter <wohlstad@xxxxxxxxx> writes:

Thanks for the replies.

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

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

I waited for someone more knowledgeable to reply and they did not! I
don't know the term "regular word grammar" and it does not come up any
interesting search hits. If you just mean "regular grammar" then the
answer is yes, subject to my other reply about the problem of
equivalence between tree grammars and the others.

--
Ben.
.

Relevant Pages

  • Re: Extended context-free grammar
    ... My intention was that the grammar above ... A satisfying assignment is an assignment that makes all ... of the set-inequalities true. ... Let G be an extended context-free grammar G with start symbol S. Let ...
    (comp.theory)
  • Re: Grammar for optional elements
    ... Negative predicates have to be regular expressions in context-free ... Thus whereas a syntactic-factor is in general equivalent to ... :to some regular grammar. ... :context-free grammar and a regular grammar is always another context-free ...
    (comp.compilers)
  • Re: Question about Programming a Turing Machine
    ... The construction of a Turing machine from a context-free grammar is ... Consider, construction of a TM for palindromes over the alphabet ...
    (sci.math)
  • Re: Why context-free?
    ... > So WHY should I use a context-free grammar? ... they accept -- you've got the grammar right there. ... parser accepts, ... of the UNIX system programmer's manual the Bourne ...
    (comp.compilers)