Skip to main content
SpringerLink
Log in

Übertragung automatentheoretischer Sätze auf Chomsky-Sprachen

Transfer of automaton-theoretical propositions to Chomsky languages

  • Published:
Computing Aims and scope Submit manuscript

Zusammenfassung

Für endliche Automaten hat man ihrem Wesen nach zwei verschiedene Äquivalenzdefinitionen, die sich dann als gleich herausstellen. Die eine Definition beruht auf der Wirkung des Automaten nach außen, die andere geht von der inneren Struktur des Automaten aus. Letztere Definition wird hier R(eduktion)-Äquivalenz genannt.

Bei der Übertragung dieser Äquivalenzbegriffe aufChomsky-Sprachen und verwandte formale Sprachen ergibt sich für dieR-Äquivalenz eine ganze Reihe von Möglichkeiten. Es wird hier über die Ergebnisse berichtet, die in diesem Zusammenhang bis jetzt erzielt wurden.

Summary

For finite automata one has two different comprehensions of equivalence which prove to be equal. One of the definitions calledR-equivalence rests on the internal structure of the automata. The other equivalence concerns those automata which cannot be distinguished by any experiments.

The extension of these equivalences to theChomsky languages and related languages leads to different possibilities for the definitions ofR-equivalences. The paper summarizes the results which are proved at this moment.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Literatur

  1. Beyer, G.: Die Erweiterung von Schaltwerken. Techn. Bericht der Fa. Telefunken1965.

  2. Brinkmann, H.-B., undD. Puppe: Kategorien und Funktoren. Lecture Notes in Mathematics. (Ed.A. Dold, R. Eckmann). Springer-Verlag. 1966.

  3. Büchi, J. R.: Theorie der endlichen automaten. Vorlesung an der Universität in Mainz (1961–1962). Nicht veröffentlicht.

  4. Chomsky, N.: Three Models for the Description of Language. IRE Trans. on Inform. Theory, IT-2,1956.

  5. Chomsky, N., andG. A. Miller: Finite State Languages. Information and Control1, (1958).

  6. Chomsky, N., andM. P. Schützenberger: The Algebraic Theory of Contextfree Languages, in: Computer Programming and Formal Systems. (Ed.:Braffort andHirschberg). Amsterdam: North-Holland Publishing Comp. 1963.

    Google Scholar 

  7. Deussen, P.: On the Algebraic Theorie of Finite Automata. ICC Bulletin4, (1966).

  8. Eickel, J., W. Lohner undH. Langmaack: Kapitel über Mehrdeutigkeit vonChomsky-0-Sprachen. Erscheint in Lecture Notes in Mathematics. (Ed.:A. Dold, R. Eckmann). Springer-Verlag.

  9. Ginsburg, S.: An Introduction to Mathematical Machine Theory. Addison-Wesley. 1962.

  10. Hartmanis, J.: On the State Assignment Problem for Sequential Machines I, IRE-Trans. EC-10, (1961).

  11. Hartmanis, J., andR. E. Stearns: On the State Assignment Problem for Sequential Machines II. IRE-Trans. EC-10, (1961).

  12. Hotz, G.: Algebraisierung des Syntheseproblems von Schaltkreisen. EIK1, (1965).

  13. Hotz, G.: Homomorphie und Äquivalenz formaler Sprachen. 3. Kolloquium über Automatentheorie. (Ed.:W. Händler, E. Peschl, H. Unger). Basel: Birkhäuser-Verlag. 1967.

    Chapter  Google Scholar 

  14. Hotz, G.: Eindeutigkeit und Mehrdeutigkeit formaler Sprachen. EIK2, (1966).

  15. Hotz, G.: Sprachen mit endlich vielen Zuständen. Math. Zeitschrift104, (1968).

  16. Hotz, G.: Erzeugung formaler Sprachen durch gekoppelte Ersetzungen. 4. Kolloquium über Automatentheorie vom 5.–6. 10. 1967 in München. (Ed.:F. L. Bauer, K. Samelson. Math. Institut der TH München).

  17. Kohavi, Z.: Secondary State Assignment for Sequential Machines. IEEE-Trans. EC-13, (1964).

  18. Krohn, K. B., andJ. L. Rhodes: Algebraic Theorie of Machines, in: Proceedings of the Symposium on Mathematical Theory of Automata, 1962. Polytechnic Press of the Polytechnic Institute of Brooklyn.

  19. Mealy, G. H.: Method for Syntheszing Sequential Circuits. Bell System Techn. J.34, (1955).

  20. Mitchell, B.: Theory of Categories. New York: Academic Press. 1965.

    MATH  Google Scholar 

  21. Moore, E. F.: Gedankenexperiments on Sequential Machines, inG. E. Shannon andJ. McCarthy: Automata Studies. Princeton University Press. 1956.

  22. Myhill: Linear Bounded Automata. WADD Techn. Note, No. 60-165. Wright-Patterson Air Force Base. Ohio. 1960.

  23. Rabin, M. O., andD. Scott: Finite Automata and Their Decision Problems. IBM Journal2, 114–125 (1959).

    Article  MathSciNet  MATH  Google Scholar 

  24. Schnorr, C. P.: Homomorphismen kontextfreier Sprachen. Erscheint demnächst.

  25. Schnorr, C. P.: Vier Entscheidbarkeitsprobleme für kontextsensitive Sprachen. Erscheint demnächst in der EIK.

  26. Schnorr, C. P., undH. Walter: Pullbackkonstruktionen bei Semi-Thuesystemen. Erscheint demnächst in der EIK.

  27. Walter, H.: Pullbackkonstruktionen bei Semi-Thuesystemen. 4. Kolloquium über Automatentheorie4, (Ed.Bauer undSamelson, München).

  28. Walter, H.: Erweiterungen von endlichen Automaten. Erscheint demnächst in der EIK.

  29. Yoeli, M.: The Cascade Decomposition of Sequential Machines. IRE Trans. EC-10, (1961).

Download references

Author information

Authors and Affiliations

  1. Institut für Angewandte Mathematik und Rechenzentrum, Universität des Saarlandes, D-66, Saarbrücken, Bundesrepublik Deutschland

    G. Hotz

Authors
  1. G. Hotz
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Hauptvortrag auf der Jahrestagung der GAMM 1968 in Prag.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hotz, G. Übertragung automatentheoretischer Sätze auf Chomsky-Sprachen. Computing 4, 30–42 (1969). https://doi.org/10.1007/BF02236540

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02236540

Search

Navigation