“Structural connections” in formal languages

ABSTRACT

This paper defines the concept of “structural connection” in a mechanical language in an attempt to classify various formal languages according to the complexity of parsing structures on strings in the languages. Languages discussed vary in complexity from those with essentially no structure at all to languages which are self-defining. The relationship between some existing recognition techniques for several language classes is examined, as well as implications of language structure on the complexity of automatic recognizers.

REFERENCES

• 1: CHOMSKY, N. On certain formal properties of grammars. Informat. Contr. 2, 137,167.
• 2: ----. A note on phrase structure grammars. Informat. Contr. 2, 393-395.
• 3: PAUL, M. A General Processor for Certain Formal Languages. Gymbalie Languages in Data Processing, Gordon and Breach, London 1962, pp. 65-74.
• 4: EICKEL, J., PAUL, M., BAUER, F. L., SAMUELSON, K. "A Syntax Controlled Generator of Formal Language Processors." Inst. fur Ant. Math. Univ. Mainz. (September, 1962).
• 5: BACKU8, J. W. The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. Proc. Internat. Conference on Information Processing, UNESCO, June, 1959, pp. 125-132.
• 6: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 7: Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Design, Languages, Performance, Theory