On grammar forms with terminal context

Research paper by H. A. Maurer, D. Wood

Indexed on: 01 Dec '76Published on: 01 Dec '76Published in: Acta Informatica


A context-free grammar form G defines a family of context-free grammars {ie397-01}(G). In this paper {ie397-02}(G) is extended to give the family of terminal context grammars {ie397-03}(G), which were introduced by Book [4]. It is shown that the families of languages defined by {ie397-04}(G) and {ie397-05}(G) are equal when G is an ɛ-free context-free grammar form. This generalizes the result of Book [4] for context-free grammars and underlines the usefulness of the notion of grammar forms in formal language theory.