Context-free grammars on trees

ABSTRACT

In this paper we discuss still another version of indexed grammars 1 and macro grammars3,gaining some geometric intuition about the structure of these systems. An ordinary context-free grammar is a rewriting system for strings; we find that a macro grammar is a rewriting system for trees. CF grammars on strings form a special case since strings can be thought of as trees without branching nodes. We consider the special case of finite-state grammars in this report. We define the tree analogue of a non deterministic generalized sequential machine and obtain results about the domain and range of such a mapping. We relate these results to the theory of generalized finite automata6.

REFERENCES

• 1: Aho, A. V., Indexed grammars—an extension of context-free grammars. IEEE Conf. Record, Symp. on Switching and Automata Theory (Oct., 1967).
• 2: Bar-Hillel, Y., M. Perles and E. Shamir, On formal properties of simple phrase structure grammars. Z. Phonetik Sprachwiss. Kommunikat 14 (1961), 143-172.
• 3: Fischer, M., Grammars with macro-like productions. IEEE Conf. Record, Symp. on Switching and Automata Theory (Oct., 1968).
• 4: Knuth, D., Semantics of context-free languages. Math. Systems Theory, vol. 2, no. 2 (June, 1968), pp. 127-158.
• 5: Petrone, L., Syntax-directed mappings of context-free languages. IEEE Conf. Record, Symp. on Switching and Automata Theory (Oct., 1968).
• 6: Thatcher, J. W. and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Systems Theory, vol. 2, no. 1 (March, 1968), pp. 57-81.
• 7: Thatcher, J. W., Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comp. Sys. Sci., vol. 1, no. 4 (Dec., 1967), pp. 317-322.
• 8: Rounds, W. C., Trees, transducers, and transformations. Ph.D. thesis, Stanford Univ., 1968.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Languages, Theory