Overview

Der Inhalt dieses Buches gehort zum mittlerweile festen Reper- toire des theoretischen Teils der Informatik. Den Schwerpunkt der angestellten Untersuchungen bilden die kontextfreien Sprachen, deren An endungen bei weitem die interessantesten sind. Die Theorie w rd in ""klassischen Bahnen"" entwickelt, urn eine breite Darstellung der spezifischen Beweismethoden zu er- moglichen, da diese ja haufig auch schon Losungsalgorithmen fur die zentralen Problemstellungen implizieren. Dadurch ist der Charakter einer Einfuhrung weitgehend gewahrt. Wir hoffen, daE so einerseits dem theoretisch Interessierten ein Zugang zu den formalen Sprachen eroffnet und somit auch der Einstieg in die neuere Theorie auf diesem Gebiet ermoglicht wird, daE anderer- seits derjenige, der formale Sprachen weitgehend fur verschie- dene Probleme der Programmierung, insbesondere fur den Ober- setzerbau verwendet, einen Oberblick uber die sprachtheoreti- schen Hilfsmittel gewinnt. Dieser Zielsetzung dienen auch die im AnschluE an die einzelnen Kapitel aufgefuhrten Aufgaben. Unter diesen befinden sich daher solche, die weiterfuhrenden Problemstellungen gewidmet sind, wie auch solche, die die innerhalb des Textes vermittelten Ge- dankengange vertiefen sollen. Die Angabe von Losungen solI nach unserer Vorstellung den Leser in die Lage versetzen, sein Ver- standnis des Textes selbst zu kontrollieren. Wir glauben, daE einfuhrende Bucher stets diese Moglichkeit offenhalten sollten. Auf ein umfangreiches Literaturverzeichnis haben wir verzichtet, da uber die zitierten Bucher leicht der AnschluE an neuere Ent- wicklungen in der Theorie der formalen Sprachen hergestellt werden kann. Bei der Losung der Aufgaben haben wir groEe Unterstutzung seitens Frau Dr. B. Schinzel, Dipl. -Math. W. Kern, Dipl. -Math.

Full Product Details

Author:   Heinrich Becker
Publisher:   Springer Fachmedien Wiesbaden
Imprint:   Vieweg+Teubner Verlag
Edition:   1977 ed.
Dimensions:   Width: 15.50cm , Height: 1.50cm , Length: 23.50cm
Weight:   0.433kg
ISBN:  

9783528033231

ISBN 10:   3528033231
Pages:   271
Publication Date:   01 January 1977
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.
Language:   German

Table of Contents

I. Einfuhrung in die Theorie der formalen Sprachen.- I.1 Naturliche Sprachen.- I.2 Die grundlegenden Definitionen.- I.3 Auswertung arithmetischer Ausdrucke und (kontextfreie) Grammatiken.- I.4 Definition von Programmiersprachen durch kontextfreie Grammatiken.- I.5 Formale Erreichbarkeit von Prozeduren.- I.6 Fragestellungen.- I.6.1 Wort-und AEquivalenzprobleme.- I.6.2 Eindeutigkeit und Mehrdeutigkeit.- I.6.3 Hierarchiefragen und Abschlusseigenschaften.- I.6.4 Mathematische Maschinen und Grammatiken.- I.6.5 Strukturuntersuchungen.- II. Regelsprachen.- II. 1 Die Chomsky-Hierarchie.- II.2 Der Hierarchie-Nachweis.- II.3 Struktursatze.- II.3.1 Die Klasse Ch-1.- II.3.2 Chomsky-reduzierte Grammatiken.- II.3.3 Die Chomsky-Normalform.- II.3.4 Der Satz von Bar'Hillel-Perles-Shamir.- II.3.5 Der Hierarchie-Nachweis.- III. Mathematische Maschinen.- III. 1 Die Turing-Maschine.- III. 1.1 Definition der Turing-Maschine.- III. 1.2 Turing-Maschinen, Regelsysteme und Ch-O-Sprachen.- III.2 Der linear beschrankte Automat.- III.2.1 Der deterministische und der nichtdeterministische linear beschrankte Automat.- III.2.2 dlba, nlba und kontextsensitive Sprachen.- III.3 Der Kellerautomat.- III.3.1 Definition des Automaten.- III.3.2 Kellerautomaten und kontextfreie Sprachen.- III.4 Der endliche Akzeptor.- III.4.1 Definition des endlichen Akzeptors.- IV. Abschlusseigenschaften.- IV. 1 Regulare Mengen.- IV.2 Der Substitutionssatz.- IV.3 Der Abschluss gegen Durchschnitt und Komplement.- IV.4 Zusammenfassung der Ergebnisse.- IV.5 Automateninduzierte Abbildungen.- IV.5.1 Sequentielle UEbersetzer.- IV.5.2 Kellerubersetzer.- V. Entscheklbarkeit.- V.1 Entscheidbare Probleme.- V. 1.1 Das Wortproblem fur kontextsensitive Sprachen.- V. 1.2 Das Wortproblem und verwandte Probleme bei kontextfreien Sprachen.- V.1.3 Das AEquivalenzproblem fur einseitig lineare Grammatiken.- V.2 Nichtentscheidbare Probleme.- V.2.1 Das Wortproblem fur Semi-Thue-Systeme und fur Ch-O-Sprachen.- V.2.2 Das Postsche Korrespondenzproblem.- V.2.3 Unentscheidbare Probleme bei kontextfreien Grammatiken.- V.2.4 Zwei nichtentscheidbare Probleme bei kontextsensitiven Grammatiken.- VI. Eindeutigkeit.- VI.1 Die Problemstellung.- VI.2 Formalisierung des Ableitungsprozesses.- VI.3 Nicht wesentlich verschiedene Ableitungen.- VI.4 Veranschaulichung durch Baume.- VI.5 Weitere Eigenschaften der Relation ? .- VI.6 Eindeutige Grammatiken und eindeutige Sprachen.- VI.7 Inharente Mehrdeutigkeit.- VII. Eine Einfuhrung in die syntaktische Analyse.- VII.1 Die Problemstellung.- VII.2 Ein Turingmaschinenmodell zur Syntaxanalyse.- VII.3 Die Greibach-Normalform.- VII.4 Die schwierigste kontextfreie Sprache.- VII.5 Der Satz von Chomsky-Schutzenberger.- Loesungen der UEbungsaufgaben.- Symbole und Bezeichnungen.- Stichwortverzeichnis.

Reviews

Author Information

Tab Content 6

Author Website:  

Countries Available

All regions