Grammars with generalized contextfree rules and their tree automata

Hugo Volger (University of Passau)


The domain of locality of the derivation trees of a contextfree
grammar (=cfg) consists of a node together with its successor
nodes. As a means to study more general classes of trees we introduce
classes of generalized cfg's which are based on the same domain of
locality. Fix a set X of expressions for defining sets of words
i.e. sentential forms.  An X-production is a pair (s,e) where s is a
nonterminal and e is an expression.  The words u satisfying e
determine the associated set of productions for s which may be
infinite. Now the usual definitions can be extended in a uniform
manner to generalized cfg's, in particular X-cfg's. - We obtain
classes of grammars which are weakly equivalent to cfg's if all
expressions used are required to define contextfree languages. Beside
the classical example of the extended cfg's of Thatcher and Wright
which ar e based on regularexpressions we obtain ID/LP-grammars, the
state-transition grammars of K.-M.Schneider which admit left-to-right
parsing schemata, as well as grammars which are based on propositional
modal logics with modal operators for the local relations of left and
right successor. The latter case include grammars with partially
specified contextfree rules.  To be able to deal with grammars like
linear indexed grammars one has to replace words by headed words where
the nonterminals carry a stack value and admit stack operations in the
productions. Using sentential forms as values one obtains grammars in
the control hierarchy. - The equivalence between the cfg's and the
non deterministic tree automata and the less known bipartite grammar
graphs of A.Palm can be lifted to generalized cfg's. The proof makes
use of production names which can be viewed as states of a tree
automaton.