reine Buchbestellungen ab 5 Euro senden wir Ihnen Portofrei zuDiesen Artikel senden wir Ihnen ohne weiteren Aufpreis als PAKET

Automaten Sprachen Berechenbarkeit
Grundkurs Angewandte Informatik IV
Wolffried Stucky & Rudolf Herschel

Print on Demand - Dieser Artikel wird für Sie gedruckt!

54,99 €

inkl. MwSt. · Portofrei
Dieses Produkt wird für Sie gedruckt, Lieferzeit ca. 14 Werktage
Menge:

Automaten Sprachen Berechenbarkeit

Produktbeschreibung

1 Mathematische Grundlagen.- 1.1 Mengen und Relationen.- 1.2 Funktionen und Verknüpfungen.- 1.3 Halbgruppen und Monoide.- 2 Automaten.- 2.1 Endliche Automaten.- 2.1.1 Beispiele für endliche Automaten.- 2.1.2 Endliche Automaten ohne Ausgabe.- 2.1.3 Endliche Automaten mit Ausgabe.- 2.1.4 Äquivalenz und Minimierung endlicher Automaten.- 2.1.5 Nichtdeterministische endliche Automaten.- 2.2 Kellerautomaten.- 3 Formale Sprachen.- 3.1 Klassifizierung und Übersicht.- 3.2 Reguläre Sprachen.- 3.3 Semi-Thue-Systeme und Chomsky-Grammatiken.- 3.3.1 Semi-Thue-Systeme.- 3.3.2 Die Chomsky-Hierarchie.- 3.3.3 Typ-3-Sprachen (reguläre Sprachen).- 3.3.4 Typ-2-Sprachen (kontextfreie Sprachen).- 3.3.5 Typ-1-Sprachen (kontextsensitive Sprachen).- 3.3.6 Typ-0-Sprachen (allgemeine Sprachen).- 4 Turing-Maschinen, Algorithmen und berechenbare Funktionen.- 4.1 Algorithmen, Berechenbarkeit und Entscheidbarkeit im intuitiven Sinne.- 4.2 Turing-Maschinen.- 4.2.1 Das Maschinenmodell.- 4.2.2 Turing-Maschinen als Akzeptoren.- 4.2.3 Turing-Berechenbarkeit und -Entscheidbarkeit.- 4.2.4 Die Simulation von Turing-Maschinen und das Halteproblem.- 4.2.5 Turing-Maschinen mit linearer Bandbeschränkung.- 4.3 Berechenbare Funktionen.- 4.3.1 Primitiv rekursive Funktionen.- 4.3.2 µ-rekursive Funktionen.- 4.4 Sprachklassen und Automaten im Überblick.- 4.4.1 Entscheidbare Sprachen.- 4.4.2 Überblick.- Lösungen.
Der Begriff der formalen Sprache ist grundlegend für viele Bereiche der angewandten und theoretischen Informatik, sei es im Bereich der Programmiersprachen, im Compilerbau oder auch in Datenmanipulations- und Abfragesprachen oder Datenbanktechnologie. Ausgehend von motivierenden Beispielen werden die klassischen analysierenden und erzeugenden Systeme formaler Sprachen untersucht: Der Hierarchie der Automaten, von endlichen Automaten über Kellerautomaten bis hin zu Turing-Maschinen, wird die Hierarchie der Chomsky-Grammatiken gegenübergestellt, wobei die einzelnen Sprachklassen diskutiert und klar gegeneinander abgegrenzt werden. Schließlich erfolgt die Darstellung grundlegender Begriffe wie "Algorithmus", "Berechenbarkeit", Entscheidbarkeit", etc. Die Bedeutung dieser Begriffe für die Informatik im allgemeinen und für die Theorie formaler Sprachen im speziellen wird herausgearbeitet. Ziel des Bandes ist es, auf leicht verständliche und dennoch präzise Weise eine Einführung in diese wichtigen Gebiete der Informatik zu geben. Insbesondere soll beim Leser ein Verständnis für viele methodischen Grundlagen - etwa für die Konzepte von Programmiersprachen - entwickelt werden. Das Buch ist im Rahmen des http://medoc.informatik.tu-muenchen.de/deutsch/medoc.html>MeDoc-Projektes in die elektronische Informatik-Bibliothek aufgenommen worden und steht über das Projekt http://InterDoc.OFFIS.Uni-Oldenburg.de>InterDoc weiterhin zur Verfügung.
Der Begriff der formalen Sprache ist grundlegend für viele Bereiche der angewandten und theoretischen Informatik, sei es im Bereich der Programmiersprachen, im Compilerbau oder auch in Datenmanipulations- und Abfragesprachen oder Datenbanktechnologie. Ausgehend von motivierenden Beispielen werden die klassischen analysierenden und erzeugenden Systeme formaler Sprachen untersucht: Der Hierarchie der Automaten, von endlichen Automaten über Kellerautomaten bis hin zu Turing-Maschinen, wird die Hierarchie der Chomsky-Grammatiken gegenübergestellt, wobei die einzelnen Sprachklassen diskutiert und klar gegeneinander abgegrenzt werden. Schließlich erfolgt die Darstellung grundlegender Begriffe wie "Algorithmus", "Berechenbarkeit", Entscheidbarkeit", etc. Die Bedeutung dieser Begriffe für die Informatik im allgemeinen und für die Theorie formaler Sprachen im speziellen wird herausgearbeitet. Ziel des Bandes ist es, auf leicht verständliche und dennoch präzise Weise eine Einführung in diese wichtigen Gebiete der Informatik zu geben. Insbesondere soll beim Leser ein Verständnis für viele methodischen Grundlagen - etwa für die Konzepte von Programmiersprachen - entwickelt werden. Das Buch ist im Rahmen des in die elektronische Informatik-Bibliothek aufgenommen worden und steht über das Projekt weiterhin zur Verfügung.
1 Mathematische Grundlagen.- 1.1 Mengen und Relationen.- 1.2 Funktionen und Verknüpfungen.- 1.3 Halbgruppen und Monoide.- 2 Automaten.- 2.1 Endliche Automaten.- 2.1.1 Beispiele für endliche Automaten.- 2.1.2 Endliche Automaten ohne Ausgabe.- 2.1.3 Endliche Automaten mit Ausgabe.- 2.1.4 Äquivalenz und Minimierung endlicher Automaten.- 2.1.5 Nichtdeterministische endliche Automaten.- 2.2 Kellerautomaten.- 3 Formale Sprachen.- 3.1 Klassifizierung und Übersicht.- 3.2 Reguläre Sprachen.- 3.3 Semi-Thue-Systeme und Chomsky-Grammatiken.- 3.3.1 Semi-Thue-Systeme.- 3.3.2 Die Chomsky-Hierarchie.- 3.3.3 Typ-3-Sprachen (reguläre Sprachen).- 3.3.4 Typ-2-Sprachen (kontextfreie Sprachen).- 3.3.5 Typ-1-Sprachen (kontextsensitive Sprachen).- 3.3.6 Typ-0-Sprachen (allgemeine Sprachen).- 4 Turing-Maschinen, Algorithmen und berechenbare Funktionen.- 4.1 Algorithmen, Berechenbarkeit und Entscheidbarkeit im intuitiven Sinne.- 4.2 Turing-Maschinen.- 4.2.1 Das Maschinenmodell.- 4.2.2 Turing-Maschinen als Akzeptoren.- 4.2.3 Turing-Berechenbarkeit und -Entscheidbarkeit.- 4.2.4 Die Simulation von Turing-Maschinen und das Halteproblem.- 4.2.5 Turing-Maschinen mit linearer Bandbeschränkung.- 4.3 Berechenbare Funktionen.- 4.3.1 Primitiv rekursive Funktionen.- 4.3.2 µ-rekursive Funktionen.- 4.4 Sprachklassen und Automaten im Überblick.- 4.4.1 Entscheidbare Sprachen.- 4.4.2 Überblick.- Lösungen.
Prof. Dr. Wolffried Stucky ist Inhaber des Lehrstuhls betriebliche Informations- und Kommunikationssysteme am Institut für Angewandte Informatik und formale Beschreibungsverfahren der Universität Karlsruhe (TH).

Inhaltsverzeichnis



1 Mathematische Grundlagen.- 1.1 Mengen und Relationen.- 1.2 Funktionen und Verknüpfungen.- 1.3 Halbgruppen und Monoide.- 2 Automaten.- 2.1 Endliche Automaten.- 2.1.1 Beispiele für endliche Automaten.- 2.1.2 Endliche Automaten ohne Ausgabe.- 2.1.3 Endliche Automaten mit Ausgabe.- 2.1.4 Äquivalenz und Minimierung endlicher Automaten.- 2.1.5 Nichtdeterministische endliche Automaten.- 2.2 Kellerautomaten.- 3 Formale Sprachen.- 3.1 Klassifizierung und Übersicht.- 3.2 Reguläre Sprachen.- 3.3 Semi-Thue-Systeme und Chomsky-Grammatiken.- 3.3.1 Semi-Thue-Systeme.- 3.3.2 Die Chomsky-Hierarchie.- 3.3.3 Typ-3-Sprachen (reguläre Sprachen).- 3.3.4 Typ-2-Sprachen (kontextfreie Sprachen).- 3.3.5 Typ-1-Sprachen (kontextsensitive Sprachen).- 3.3.6 Typ-0-Sprachen (allgemeine Sprachen).- 4 Turing-Maschinen, Algorithmen und berechenbare Funktionen.- 4.1 Algorithmen, Berechenbarkeit und Entscheidbarkeit im intuitiven Sinne.- 4.2 Turing-Maschinen.- 4.2.1 Das Maschinenmodell.- 4.2.2 Turing-Maschinen als Akzeptoren.- 4.2.3 Turing-Berechenbarkeit und -Entscheidbarkeit.- 4.2.4 Die Simulation von Turing-Maschinen und das Halteproblem.- 4.2.5 Turing-Maschinen mit linearer Bandbeschränkung.- 4.3 Berechenbare Funktionen.- 4.3.1 Primitiv rekursive Funktionen.- 4.3.2 µ-rekursive Funktionen.- 4.4 Sprachklassen und Automaten im Überblick.- 4.4.1 Entscheidbare Sprachen.- 4.4.2 Überblick.- Lösungen.