Theoretische Informatik stellt für viele Studenten ein Angstfach dar, sie gilt als abstrakt, stark formalisiert und dem Alltag entrückt. Das vorliegende Buch macht die Grundideen der Theoretischen Informatik auch für Studenten verständlich, deren erster Schwerpunkt nicht Informatik und schon gar nicht Mathematik ist. Automatentheorie, formale Sprachen und Grammatiken, Komplexität und Berechenbarkeit sind die wesentlichen Inhalte der Theoretischen Informatik, die in diesem Buch behandelt werden. Durch die Vielzahl der Beispiele, auch aus dem täglichen Leben, und den lockeren Schreibstil kann jeder interessierte Studierende die Hürde "Theoretische Informatik" nehmen - und vielleicht sogar etwas von der Faszination spüren, die von ihr ausgeht.

Autorentext
Roland Schmitz ist promovierter Mathematiker und seit 2001 Professor für Internet-Security im Studiengang Medieninformatik an der Hochschule der Medien in Stuttgart. Vorher war er sechs Jahre lang wissenschaftlicher Mitarbeiter am Technologiezentrum der Deutschen Telekom mit den Hauptarbeitsgebieten Sicherheit mobiler Kommunikation sowie Standardisierung digitaler Signaturen.

Inhalt

Über den Autor 7

Einleitung 17

Was ist theoretische Informatik? 17

Über dieses Buch 18

Wie dieses Buch aufgebaut ist 18

Symbole in diesem Buch 20

Wie Sie dieses Buch lesen sollten 20

Teil I Endliche Automaten 21

Kapitel 1 Deterministische Endliche Automaten (DFAs) 23

Einführung 23

Erste Beispiele 24

Grundlegende Definitionen 27

Symbole und Wörter 27

Die Definition eines DFAs 28

Reguläre Sprachen 30

Die erweiterte Übergangsfunktion 30

Beispiele regulärer Sprachen 31

Das Pumping Lemma 34

Minimalautomaten 38

Der Satz von Myhill und Nerode 45

DFAs mit Ausgabe (Moore- und Mealy-Automaten) 50

Aufgaben zu DFAs 54

Kapitel 2 Nichtdeterministische Endliche Automaten (NFAs) 57

Nichtdeterminismus 57

Definition eines NFA 58

Der Satz von Rabin-Scott 60

NFAs mit 𝜖-Übergängen 64

Abschlusseigenschaften regulärer Sprachen 67

Reguläre Ausdrücke 70

Stochastische Automaten und Markov-Ketten 75

Hidden Markov Models 80

Aufgaben zu NFAs 80

Kapitel 3 Kellerautomaten (PDAs) 83

Nichtdeterministische Kellerautomaten 83

Deterministische Kellerautomaten 89

Die Grenzen von PDAs 91

Aufgaben zu PDAs 92

Kapitel 4 Turing-Maschinen 93

Deterministische Turing-Maschinen 93

Turing-Berechenbarkeit 102

Mehrband-Turing-Maschinen 105

Registermaschinen 109

Nichtdeterministische Turing-Maschinen 110

Linear beschränkte Turing-Maschinen 112

Universelle Turing-Maschine (UTM) 113

Die Grenzen von Turing-Maschinen 115

Aufgaben zu Turing-Maschinen 120

Teil II Formale Sprachen 123

Kapitel 5 Grammatiken 125

Einführung 125

Ein erstes Beispiel 126

Syntaxbäume 127

Definition einer Grammatik 128

Die von einer Grammatik erzeugte Sprache 128

Wie man 𝜖-Regeln loswird 129

Das Wortproblem 131

Chomsky-Hierarchie 131

Aufgaben zu Grammatiken 133

Kapitel 6 Reguläre (Typ-3-)Sprachen 135

Beispiele für Typ-3-Sprachen 135

Das Wortproblem für Typ-3-Sprachen 136

Aufgaben zu Typ-3-Sprachen 139

Kapitel 7 Kontextfreie (Typ-2-)Sprachen 141

Erste Beispiele 141

Backus-Naur-Form (BNF) 142

Erweiterte Backus-Naur-Form (EBNF) 142

Chomsky-Normalform 144

Die Grenzen kontextfreier Sprachen 146

Ein äquivalentes Maschinenmodell 150

Deterministisch kontextfreie Sprachen 153

Das Wortproblem für kontextfreie Sprachen 154

Abschlusseigenschaften 156

Aufgaben zu kontextfreien Sprachen 157

Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159

Ein erstes Beispiel 159

Das Wortproblem für Typ-1-Sprachen 160

Das Wortproblem für Typ-0-Sprachen 161

Äquivalente Maschinenmodelle 162

Typ-0-Sprachen 162

Typ-1-Sprachen 164

Teil III Harte Probleme 167

Kapitel 9 Zeitkomplexität von Algorithmen 169

Einführende Überlegungen 169

Zeit- und Speicherkomplexität von Algorithmen 171

Die O-Notation 175

Komplexitätsklassen von Sprachen 177

Aufgaben zur Komplexität von Algorithmen 179 **Kapitel 10 Die Kl...