Matrix Equations and Normal Forms for Context-Free Grammars

ABSTRACT

The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the solution to a set of linear equations. A procedure is then given for rewriting a context-free grammar in Greibach normal form, where the replacements string of each production begins with a terminal symbol. An additional procedure is given for rewriting the grammar so that each replacement string both begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular expressions over the total vocabulary of the grammar, as is required by Greibach's procedure.

REFERENCES

• 1: ARDEN, D.N. Delayed logic and finite state machines. In Theory of Computing Machine Design, U. of Michigan Press, Ann Arbor, Mich., 1960, pp. 1-35.
• 2: BRZOZOWSKt, J. A. A survey of regular expressions and their applications. IRE Trans. EC-II, 3 (June 1962), 324-335.
• 3: ----" AND McCLusKEY, E. J., JR. Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. EC-12, 2 (April 1963), 67-76.
• 4: CHOMSKY, N. Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. II, Lute, II. D., Bush, R. R., and Galanter, E. (Eds.), Wiley, New York, 1963, pp. 323- 418.
• 5: ----- AND SCHUrZENBERUER, M. P. The algebraic theory of context-free languages. In Computer Programming and Formal Systems, Braffort, P., and Hirschberg, D. (Eds.), North- Holland Publishing Co., Amsterdam, 1963, pp. 118-161.
• 6: Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
• 7: Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
• 8: KLEENE, S. C. Representation of events in nerve nets and finite autornata. In Automata Studies, Shannon, C. E., and McCarthy, H. (Eds.), Princeton U. Press, Princeton, N. J., 1956, pp. 3-41.
• 9: McNAuGHrON, R., AND YAMADA, H. Regular expressions and state graphs for automata. IRE Trans. EC-9, 1 March 1960), 39-47.

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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Experimentation, Measurement, Performance, Theory