\(n\)-ary grammars and the description of mapping of languages. (English) Zbl 0194.31602

An \(n\)-ary grammar is a generalization of a phrase-structure grammar. It consists of a system of \(n\) terminal alphabets, \(n\) nonterminal alphabets, a set of productions and an initial \(n\)-tuple of nonterminals. Each production is an \(n\)-tuple of common productions or empty places. Similar systems have been used elsewhere for definition of languages. In the paper three different types of derivation \((\alpha,\beta\) and \(\gamma)\) are considered whose common feature is that components of a production are applied simultaneously to corresponding components of intermediate \(n\)-tuples of words. An \(\alpha\)-generation is a straightforward generalization of the usual “top-down” definition of generation in phrase structure grammars (N. Chomsky). The \(\beta\) generation can be regarded as a generalization of “bottom-up” generation used in definition of Backus normal forms. For common context-free grammars these definitions are known to be equivalent, this is not true for context-free \(n\)-ary grammars. A condition under which an \(\alpha\)-generation is also a \(\beta\)-generation is derived. The Chomsky classification of phrase-structure grammars and languages is generalized for \(n\)-ary grammars and relations. The standard closure properties and other properties of classes of relations generated by different types of \(n\)-ary grammars are studied. The class of relation defined by right-linear grammars are identical for \(\alpha\) and \(\beta\)-generations and is precisely equal to the class of relation defined by nondeterministic \(n\)-tape finite one-way nonwriting automata.
In the last section binary grammars are used to describe translations of languages. \(\beta\) and \(\gamma\) generations seem to be particularly convenient for this application. Finally, an attempt is made to classify the complexity of alphabetical mappings by the type of binary grammar which is required for their description.
Reviewer: Karel Čulik II


68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: EuDML


[1] Čulík K.: Well-translatable grammars and ALGOL-like languages. In Steel, T. B. Jr. (Ed.): Proc. IFIP Working Conference on Formal Language Description Languages. North-Holland, Amsterdam 1966, pp. 76-85.
[2] Čulík II K.: Sequential Machines with several input and output tapes. Kybernetika 3 (1967), 6, 540-559. · Zbl 0155.02001
[3] Elgot C. C., Mezei J. E.: On finite relation defined by generalized automata. IBM J. of Research and Development 9 (Jan. 1965), 1, 47-68. · Zbl 0135.00704
[4] Ginsburg S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York 1966. · Zbl 0184.28401
[5] Ginsburg S., Rose G. F.: A Characterization of Machine Mappings. The Canadian Journal of Mathematics 18 (1966), 381-388. · Zbl 0143.01903
[6] Glushkov V. M.: Introduction to Cybernetics. Academic Press, New York 1966.
[7] Lewis II P. M., Stearns R. E.: Syntax-Directed Transduction. J. ACM 15 (July 1968), 3, 465-488. · Zbl 0164.32102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.