×

Structural unambiguity of formal languages. (English) Zbl 0278.68062

From the text: The author considers the problem of the structural unambiguity of a class \(\mathcal C\) of formal grammars that is contained in the class of all semi-Thue systems (the restriction consists in that substitutions of other texts are possible only for texts of length one (i.e., for single symbols), but contains the class of context-free grammars).

MSC:

68Q45 Formal languages and automata

Software:

ALGOL 60
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] J. W. Backus F. L. Bauer J. Green C. Katz J. McCarthy P. Naur (editor) A. J. Perlis H. Rutishauser K. Samelson E. Vauquois J. H. Wegstein A. van Wijngaarden M. Woodger: Report on the Algorithmic Language ALGOL 60. Numerische Mathematik 2 (1960), 106-136. · Zbl 0089.12510
[2] H. Bottenbruch: Übersetzung von algorithmischen Formelsprachen in die Programmsprachen von Rechenmaschinen. Zeit. für math. Logik und Grundlagen der Mathematik 4 (1958), 180-221. · Zbl 0089.33201 · doi:10.1002/malq.19580041205
[3] D. G. Cantor: On the Ambiguity Problem of Backus Systems. J. Assoc. Comp. Mach. 9 (1962), 477-479. · Zbl 0114.33003 · doi:10.1145/321138.321145
[4] Noam Chomsky: On certain Formal Properties of Grammars. Information and Control 2 (1959), 137-167. · Zbl 0088.10801 · doi:10.1016/S0019-9958(59)90362-6
[5] Noam Chomsky: Three Models for the Description of Language. IRE Trans. 1, T-2, No. 3 (1956), 113-124. (Russian translation: Kibernetičeskij sbornik 2 (1961)) · Zbl 0156.25401 · doi:10.1109/TIT.1956.1056813
[6] N. Chomsky, M. P. Schützenberger: The Algebraic Theory of Context-free Languages. Computer Programming and Formal Systems (ed. by P. Braffort and D. Hirschberg), Amsterdam 1963. · Zbl 0148.00804
[7] Martin Davis: Computability and Unsolvability. New York, McGraw-Hill 1958. · Zbl 0080.00902
[8] Francois Genuys: Commentaires sur le langage Algol. Chiffres 5 (1962), 29-53. · Zbl 0100.13105
[9] Sheita A. Greibach: The Undecidability of the Ambiguity Problem for Minimal Linear Grammars. Information and Control 6 (1963), 119-125. · Zbl 0115.37007 · doi:10.1016/S0019-9958(63)90149-9
[10] Peter Zilahy Ingerman: A Syntax-Oriented Compiler for Languages whose Syntax Is Expressible in Backus Normal Form, and Some Proposed Extensions Thereto. University of Pennsylvania, The Moore School of Electrical Engineering, Philadelphia, Pennsylvania, April 1963.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.