Grammar Schemata

ABSTRACT

A solution is presented for the following problem: Determine a procedure that produces, for each full trio L of context-free languages (more generally, each trio of r.e. languages), a family of context-free (phrase structure) grammars which (a) defines L, (b) is simple enough for practical and theoretical purposes, and (c) in most cases is a subfamily of a well-known family of context-free (phrase structure) grammars for L if such a well-known family exists. (A full trio (trio) is defined to be a family of languages closed under homomorphism (&egr;-free homomorphism), inverse homomorphism, and intersection with regular sets.) The key notion in the paper is that of a grammar schema. With each grammar schema there is associated a family of interpretations. In turn, each interpretation of a grammar schema gives rise to a phrase structure grammar. Given a full trio (trio) L of context-free (r.e.) languages, one constructs a grammar schema whose interpretations (&egr;-limited interpretations) then give rise to the desired family of grammars for L.

REFERENCES

• 1: L. Boasson, An iteration theorem for one-counter languages., Proceedings of the third annual ACM symposium on Theory of computing, p.116-120, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805043]
• 2: CHOMSKY, N., AND SCHUTZEN~.RGER, M. P. The algebraic theory of context-free languages. In Computer Programming and Formal Systems, P. Braffort and D. Hirschberg, ~ds., North~ Holland Publishing Co., Amsterdam, 1963, pp. 118-161.
• 3: GINSBURa, S., AND GR~IBACH, S. Abstract families of languages. In Studies in Abstract Families of Languages, Memoirs of the American Mathematical Society, No. 87, 1969, pp. 1-32.
• 4: GINS~UaG, S., AND GREIBACH, S. Principal AFL. J. Comput. and Syst. Sci. ~ (1970), 308-339.
• 5: GINSBURG, S., AND SPANIER, E.H. Finite-turn pushdown automata. SIAM J. on Contr. ~ (1966), 429-453.
• 6: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 7: NIVAT, M. Transductions des Languages de Chomsky. Ph.D. Th., U. of Paris, 1967.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

Additional 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)

General Terms:
Languages, Performance, Theory, Verification