Abstract
In this paper the grammatical structure of the "Hardest contextfree language" L0 of Sh. Greibach 4 is analyzed and the following result is obtained : There exists a grammar G0 for L0, such that for each c.f. language L and for each c.f. grammar G in Greibach-Normalform generating L the set of derivations of words of L in G is mapped functorially into the set of derivations of the words of L0 in G0.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Literaturverzeichnis
Aho,Ullman The Theory of Parsing,Translation and Compiling Vol. I Parsing,Prentice-Hall
Estenfeld Ein funktorieller Zusammenhang zwischen einer beliebigen kontextfreien Sprache und der Greibachsprache Diplomarbeit, Saarbrücken 1976
Greibach A new Normalform Theorem for Contextfree Phrase Structure Grammars JACM 12,1965
Greibach Remarks on Context-Free Languages and Polynomial Time Recognition Dep. ofSystem Science University of California, Los Angeles
Hopcroft-Ullman Formal Languages and their Relation to Automata Addison Wesley 1969
Hotz,Claus Automatentheorie und formale Sprachen Band III Formale Sprachen, BI-Hochschulskripten
Rights and permissions
Copyright information
© 1977 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Estenfeld, K. (1977). Strukturelle Untersuchungen zur schwersten kontextfreien Sprache. In: Theoretical Computer Science. Lecture Notes in Computer Science, vol 48. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-08138-0_9
Download citation
DOI: https://doi.org/10.1007/3-540-08138-0_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08138-8
Online ISBN: 978-3-540-37389-6
eBook Packages: Springer Book Archive