Artikel werden geladen
Autoren:
Verlag:
Pearson Studium Weitere Titel dieses Verlages anzeigen
| Kapitel 1 Automaten: Die Grundlagen und Methoden | ||
| 1.1 Wozu dient das Studium der Automatentheorie?............. | ||
| 1.1.1 Einführung in endliche Automaten ................. | ||
| 1.1.2 Strukturelle Repräsentationen...................... | ||
| 1.1.3 Automaten und Komplexität....................... | ||
| 1.2 Einführung in formale Beweise........................... | ||
| 1.2.1 Deduktive Beweise............................... | ||
| 1.2.2 Reduktion auf Definitionen........................ | ||
| 1.2.3 Andere Formen von Sätzen........................ | ||
| 1.2.4 Sätze, die keine Wenn-dann-Aussagen zu sein scheinen . | ||
| 1.3 Weitere Formen von Beweisen............................ | ||
| 1.3.1 Beweise der Äquivalenz von Mengen................ | ||
| 1.3.2 Die Umkehrung ................................. | ||
| 1.3.3 Beweis durch Widerspruch........................ | ||
| 1.3.4 Gegenbeispiele.................................. | ||
| 1.4 Induktive Beweise ..................................... | ||
| 1.4.1 Induktive Beweise mit ganzen Zahlen ............... | ||
| 1.4.2 Allgemeinere Formen der Induktion mit ganzen Zahlen . | ||
| 1.4.3 Strukturelle Induktion............................ | ||
| 1.4.4 Gegenseitige Induktion ........................... | ||
| 1.5 Die zentralen Konzepte der Automatentheorie............... | ||
| 1.5.1 Alphabete...................................... | ||
| 1.5.2 Zeichenreihen .................................. | ||
| 1.5.3 Sprachen....................................... | ||
| 1.5.4 Probleme....................................... | ||
| Zusammenfassung von Kapitel 1.......................... | ||
Inhaltsverzeichnis | ||
Vorwort | ||
Vorwort zur deutschen Auflage | ||
| Kapitel 2 Endliche Automaten | 61 | |
| 2.1 | Eine informelle Darstellung endlicher Automaten | 63 |
| 2.1.1 | Die Grundregeln | 63 |
| 2.1.2 | Das Protokoll | 64 |
| 2.1.3 | Die Automaten dazu befähigen, Eingaben zu ignorieren | 66 |
| 2.1.4 | Das gesamte System aus Automaten darstellen | 68 |
| 2.1.5 Mithilfe des Produktautomaten die Gültigkeit des Protokolls | ||
| überprüfen | 70 | |
| 2.2 | Deterministische endliche Automaten | 71 |
| 2.2.1 | Definition eines deterministischen endlichen Automaten | 71 |
| 2.2.2 | Wie ein DEA Zeichenreihen verarbeitet | 72 |
| 2.2.3 | Einfachere Notationen für DE As | 74 |
| 2.2.4 | Die Ubergangsfunktion auf Zeichenreihen erweitern | 75 |
| 2.2.5 | Die Sprache eines DEA | 79 |
| 2.2.6 | Übungen zum Abschnitt 2.2 | 79 |
| 2.3 | Nichtdeterministische endliche Automaten | 82 |
| 2.3.1 Eine informelle Sicht auf nichtdeterministische endliche | ||
| Automaten | 83 | |
| 2.3.2 | Definition nichtdeterministischer endlicher Automaten | 85 |
| 2.3.3 | Die erweiterte Übergangsfunktion | 86 |
| 2.3.4 | Die Sprache eines NEA | 87 |
| 2.3.5 Äquivalenz deterministischer und nichtdeterministischer | ||
| endlicher Automaten | 88 | |
| 2.3.6 | Ein ungünstiger Fall für die Teilmengenkonstruktion | 93 |
| 2.3.7 | Übungen zum Abschnitt 2.3 | 95 |
| 2.4 | Eine Anwendung: Textsuche | 97 |
| 2.4.1 | Zeichenreihen in Texten finden | 97 |
| 2.4.2 Nichtdeterministische endliche Automaten für die | ||
| Textsuche | 98 | |
| 2.4.3 | Ein DEA, um die Menge von Schlüsselwörtern zu erkennen | 99 |
| 2.4.4 | Übungen zum Abschnitt 2.4 | 101 |
| 2.5 | Endliche Automaten mit ¿-Übergängen | 101 |
| 2.5.1 | Verwendungen von ¿ -Übergängen | 102 |
| 2.5.2 | Die formale Notation eines ¿-NEA | 103 |
| 2.5.3 | ¿-Hüllen | 104 |
| 2.5.4 | Erweiterte Übergänge und Sprachen für ¿-NEAs | 105 |
| 2.5.5 | ¿-Übergänge eliminieren | 107 |
| 2.5.6 | Übungen zum Abschnitt 2.5 | 110 |
| Zusammenfassung von Kapitel 2 | 111 | |
| Kapitel 3 Reguläre Ausdrücke und Sprachen | 113 | |
| 3.1 | Reguläre Ausdrücke | 114 |
| 3.1.1 | Die Operatoren regulärer Ausdrücke | 115 |
| 3.1.2 | Reguläre Ausdrücke bilden | 117 |
| 3.1.3 Auswertungsreihenfolge der Operatoren regulärer | ||
| Ausdrücke | 120 | |
| 3.1.4 | Übungen zum Abschnitt 3.1 | 121 |
| 3.2 | Endliche Automaten und reguläre Ausdrücke | 122 |
| 3.2.1 | Von DE As zu regulären Ausdrücken | 122 |
| 3.2.2 DEA durch die Eliminierung von Zuständen | ||
| in reguläre Ausdrücke umwandeln | 128 | |
| 3.2.3 | Reguläre Ausdrücke in Automaten umwandeln | 134 |
| 3.2.4 | Übungen zum Abschnitt 3.2 | 138 |
| 3.3 | Anwendungen regulärer Ausdrücke | 140 |
| 3.3.1 | Reguläre Ausdrücke in Unix | 140 |
| 3.3.2 | Lexikalische Analyse | 142 |
| 3.3.3 | Textmuster finden | 144 |
| 3.3.4 | Übungen zum Abschnitt 3.3 | 146 |
| 3.4 | Algebraische Gesetze für reguläre Ausdrücke | 147 |
| 3.4.1 | Assoziativität und Kommutativität | 147 |
| 3.4.2 | Identitäten und Annihilatoren | 148 |
| 3.4.3 | Distributivgesetze | 149 |
| 3.4.4 | Das Idempotenzgesetz | 150 |
| 3.4.5 | Gesetze bezüglich der Hüllenbildung | 150 |
| 3.4.6 | Gesetze für reguläre Ausdrücke entdecken | 151 |
| 3.4.7 Test eines für reguläre Ausdrücke geltenden Gesetzes | ||
| der Algebra | 154 | |
| 3.4.8 | Übungen zum Abschnitt 3.4 | 156 |
| Zusammenfassung von Kapitel 3 | 157 | |
| Kapitel 4 Eigenschaften regulärer Sprachen | 159 | |
| 4.1 | Beweis der Nichtregularität von Sprachen | 160 |
| 4.1.1 | Das Pumping-Lemma für reguläre Sprachen | 161 |
| 4.1.2 | Anwendungen des Pumping-Lemmas | 162 |
| 4.1.3 | Übungen zum Abschnitt 4.1 | 164 |
| 4.2 | Abschluss-Eigenschaften regulärer Sprachen | 166 |
| 4.2.1 Abgeschlossenheit regulärer Sprachen bezüglich | ||
| Boolescher Operationen | 166 | |
| 4.2.2 | Spiegelung | 173 |
| 4.2.3 | Homomorphismus | 174 |
| 4.2.4 | Inverser Homomorphismus | 176 |
| 4.2.5 | Übungen zum Abschnitt 4.2 | 182 |
| 4.3 | Entscheidbarkeits-Eigenschaften regulärer Sprachen | 185 |
| 4.3.1 | Wechsel zwischen Repräsentationen | 186 |
| 4.3.2 | Prüfen, ob eine reguläre Sprache leer ist | 189 |
| 4.3.3 | Zugehörigkeit zu einer regulären Sprache prüfen | 190 |
| 4.3.4 | Übungen zum Abschnitt 4.3 | 191 |
| 4.4 | Äquivalenz und Minimierung von Automaten | 191 |
| 4.4.1 | Prüfen, ob Zustände äquivalent sind | 192 |
| 4.4.2 | Prüfen, ob reguläre Sprachen äquivalent sind | 195 |
| 4.4.3 | Minimierung von DEAs | 198 |
| 4.4.4 | Warum minimierte DEAs unschlagbar sind | 201 |
| 4.4.5 | Übungen zum Abschnitt 4.4 | 203 |
| Zusammenfassung von Kapitel 4 | 204 | |
| Kapitel 5 Kontextfreie Grammatiken und Sprachen | 205 | |
| 5.1 | Kontextfreie Grammatiken | 206 |
| 5.1.1 | Ein informelles Beispiel | 206 |
| 5.1.2 | Definition kontextfreier Grammatiken | 208 |
| 5.1.3 | Ableitungen mithilfe einer Grammatik | 210 |
| 5.1.4 | Links-und rechtsseitige Ableitungen | 213 |
| 5.1.5 | Die Sprache einer Grammatik | 215 |
| 5.1.6 | Satzformen | 216 |
| 5.1.7 | Übungen zum Abschnitt 5.1 | 217 |
| 5.2 | Parse-Bäume | 219 |
| 5.2.1 | Parse-Bäume aufbauen | 219 |
| 5.2.2 | Der Ergebnis eines Parse-Baums | 221 |
| 5.2.3 | Inferenz, Ableitungen und Parse-Bäume | 222 |
| 5.2.4 | Von Inferenzen zu Bäumen | 223 |
| 5.2.5 | Von Bäumen zu Ableitungen | 225 |
| 5.2.6 | Von Ableitungen zu rekursiven Inferenzen | 228 |
| 5.2.7 | Übungen zum Abschnitt 5.2 | 230 |
| 5.3 | Anwendungen kontextfreier Grammatiken | 231 |
| 5.3.1 | Parser | 231 |
| 5.3.2 | Der YACC-Parsergenerator | 234 |
| 5.3.3 | Markup-Sprachen | 235 |
| 5.3.4 | XML und Dokumenttypdefinitionen | 238 |
| 5.3.5 | Übungen zum Abschnitt 5.3 | 244 |
| 5.4 | Mehrdeutigkeit von Grammatiken und Sprachen | 245 |
| 5.4.1 | Mehrdeutige Grammatiken | 246 |
| 5.4.2 | Mehrdeutigkeit aus Grammatiken tilgen | 248 |
| 5.4.3 Linksseitige Ableitungen als Möglichkeit zur Beschreibung | ||
| von Mehrdeutigkeit | 251 | |
| 5.4.4 | Inhärente Mehrdeutigkeit | 252 |
| 5.4.5 | Übungen zum Abschnitt 5.4 | 255 |
| Zusammenfassung von Kapitel 5 | 256 | |
| Kapitel 6 Pushdown-Automaten | 259 | |
| 6.1 | Definition des Pushdown-Automaten | 260 |
| 6.1.1 | Informelle Einführung | 260 |
| 6.1.2 | Die formale Definition von Pushdown-Automaten | 262 |
| 6.1.3 | Eine grafische Notation für PDAs | 264 |
| 6.1.4 | Unmittelbare Beschreibungen eines PDA | 265 |
| 6.1.5 | Übungen zum Abschnitt 6.1 | 269 |
| 6.2 | Die Sprachen eines PDA | 270 |
| 6.2.1 | Akzeptanz durch Endzustand | 270 |
| 6.2.2 | Akzeptanz durch leeren Stack | 272 |
| 6.2.3 | Vom leeren Stack zum Endzustand | 272 |
| 6.2.4 | Vom Endzustand zum leeren Stack | 276 |
| 6.2.5 | Übungen zum Abschnitt 6.2 | 278 |
| 6.3 | Äquivalenz von PDAs und kontextfreien Grammatiken | 279 |
| 6.3.1 | Von Grammatiken zu PDAs | 280 |
| 6.3.2 | Von PDAs zu Grammatiken | 283 |
| 6.3.3 | Übungen zum Abschnitt 6.3 | 288 |
| 6.4 | Deterministische Pushdown-Automaten | 289 |
| 6.4.1 | Definition eines deterministischen PDA | 290 |
| 6.4.2 | Reguläre Sprachen und deterministische PDAs | 291 |
| 6.4.3 | DPDAs und kontextfreie Sprachen | 292 |
| 6.4.4 | DPDAs und mehrdeutige Grammatiken | 293 |
| 6.4.5 | Übungen zum Abschnitt 6.4 | 294 |
| Zusammenfassung von Kapitel 6 | 295 | |
| Kapitel 7 Eigenschaften kontextfreier Sprachen | 297 | |
| 7.1 | Normalformen kontextfreier Grammatiken | 298 |
| 7.1.1 | Eliminierung unnützer Symbole | 298 |
| 7.1.2 | Berechnung der erzeugenden und erreichbaren Symbole | 301 |
| 7.1.3 | 8-Produktionen eliminieren | 302 |
| 7.1.4 | Einheitsproduktionen eliminieren | 306 |
| 7.1.5 | Chomsky-Normalform | 311 |
| 7.1.6 | Übungen zum Abschnitt 7.1 | 316 |
| 7.2 | Das Pumping-Lemma für kontextfreie Sprachen | 319 |
| 7.2.1 | Die Größe von Parse-Bäumen | 319 |
| 7.2.2 | Aussage des Pumping-Lemmas | 320 |
| 7.2.3 Anwendungen des Pumping-Lemmas für kontextfreie | ||
| Sprachen | 323 | |
| 7.2.4 | Übungen zum Abschnitt 7.2 | 326 |
| 7.3 | Abschluss-Eigenschaften kontextfreier Sprachen | 328 |
| 7.3.1 | Substitutionen | 328 |
| 7.3.2 | Anwendungen des Substitutions-Theorems | 331 |
| 7.3.3 | Spiegelung | 332 |
| 7.3.4 | Durchschnitt mit einer regulären Sprache | 332 |
| 7.3.5 | Inverse Homomorphismen | 337 |
| 7.3.6 | Übungen zum Abschnitt 7.3 | 339 |
| 7.4 | Entscheidbarkeits-Eigenschaften kontextfreier Sprachen | 341 |
| 7.4.1 Komplexität der Umwandlung von kfGs in PDAs und | ||
| umgekehrt | 342 | |
| 7.4.2 Ausführungszeit der Umwandlung in Chomsky- | ||
| Normalform | 343 | |
| 7.4.3 | Prüfen, ob eine kontextfreie Sprache leer ist | 345 |
| 7.4.4 | Die Zugehörigkeit zu einer kontextfreien Sprache prüfen | 347 |
| 7.4.5 | Vorschau auf unentscheidbare kfL-Probleme | 351 |
| 7.4.6 | Übungen zum Abschnitt 7.4 | 352 |
| Zusammenfassung von Kapitel 7 | 353 | |
| Kapitel 8 Einführung in Turing-Maschinen | 355 | |
| 8.1 | Probleme, die Computer nicht lösen können | 356 |
| 8.1.1 | Programme, die »Hello, World« ausgeben | 357 |
| 8.1.2 | Der hypothetische »Hello, World«-Tester | 359 |
| 8.1.3 | Ein Problem auf ein anderes Problem reduzieren | 362 |
| 8.1.4 | Übungen zum Abschnitt 8.1 | 365 |
| 8.2 | Die Turing-Maschine | 366 |
| 8.2.1 Das Streben danach, alle mathematischen Fragen zu | ||
| entscheiden | 367 | |
| 8.2.2 | Die Notation der Turing-Maschine | 368 |
| 8.2.3 | Unmittelbare Beschreibungen für Turing-Maschinen | 369 |
| 8.2.4 | Übergangsdiagramme für Turing-Maschinen | 373 |
| 8.2.5 | Die Sprache einer Turing-Maschine | 376 |
| 8.2.6 | Turing-Maschinen und das Halteproblem | 377 |
| 8.2.7 | Übungen zum Abschnitt 8.2 | 378 |
| 8.3 | Programmiertechniken für Turing-Maschinen | 379 |
| 8.3.1 | Speicher im Zustand | 380 |
| 8.3.2 | Mehrere Spuren | 381 |
| 8.3.3 | Unterprogramme | 383 |
| 8.3.4 | Übungen zum Abschnitt 8.3 | 386 |
| 8.4 | Erweiterungen für die einfache Turing-Maschine | 386 |
| 8.4.1 | Turing-Maschinen mit mehreren Bändern | 386 |
| 8.4.2 | Äquivalenz zwischen ein- und mehrbändigen TMn | 388 |
| 8.4.3 | Ausführungszeit und die Viele-Bänder-in-eins-Konstruktion | 390 |
| 8.4.4 | Nichtdeterministische Turing-Maschinen | 391 |
| 8.4.5 | Übungen zum Abschnitt 8.4 | 393 |
| 8.5 | Beschränkte Turing-Maschinen | 396 |
| 8.5.1 | Turing-Maschinen mit semi-unendlichen Bändern | 397 |
| 8.5.2 | Maschinen mit mehreren Stacks | 400 |
| 8.5.3 | Zählermaschinen | 403 |
| 8.5.4 | Die Leistungsfähigkeit von Zählermaschinen | 404 |
| 8.5.5 | Übungen zum Abschnitt 8.5 | 406 |
| 8.6 | Turing-Maschinen und Computer | 407 |
| 8.6.1 | Eine Turing-Maschine mit einem Computer simulieren | 407 |
| 8.6.2 | Einen Computer mit einer Turing-Maschine simulieren | 409 |
| 8.6.3 Laufzeitvergleich zwischen Computern und | ||
| Turing-Maschinen | 413 | |
| Zusammenfassung von Kapitel 8 | 416 | |
| Kapitel 9 Unentscheidbarkeit | 419 | |
| 9.1 | Eine nicht rekursiv aufzählbare Sprache | 421 |
| 9.1.1 | Binärzeichenreihen aufzählen | 421 |
| 9.1.2 | Codes für Turing-Maschinen | 422 |
| 9.1.3 | Die Diagonalisierungssprache | 423 |
| 9.1.4 | Der Beweis, dass Lj nicht rekursiv aufzählbar ist | 425 |
| 9.1.5 | Übungen zum Abschnitt 9.1 | 425 |
| 9.2 | Ein unentscheidbares Problem, das rekursiv aufzählbar ist | 426 |
| 9.2.1 | Rekursive Sprachen | 426 |
| 9.2.2 Komplemente rekursiver und rekursiv aufzählbarer | ||
| Sprachen | 427 | |
| 9.2.3 | Die universelle Sprache | 430 |
| 9.2.4 | Unentscheidbarkeit der universellen Sprache | 433 |
| 9.2.5 | Übungen zum Abschnitt 9.2 | 434 |
| 9.3 | Unentscheidbare Probleme über Turing-Maschinen | 436 |
| 9.3.1 | Reduktionen | 436 |
| 9.3.2 | Turing-Maschinen, die die leere Sprache akzeptieren | 438 |
| 9.3.3 Der Satz von Rice und Eigenschaften der rekursiv | ||
| aufzählbaren Sprachen | 441 | |
| 9.3.4 Probleme bezüglich Spezifikationen von | ||
| Turing-Maschinen | 444 | |
| 9.3.5 | Übungen zum Abschnitt 9.3 | 444 |
| 9.4 | Das Postsche Korrespondenz-Problem | 446 |
| 9.4.1 | Definition des Postschen Korrespondenz-Problems | 446 |
| 9.4.2 | Das »modifizierte« PKP | 449 |
| 9.4.3 | Fertigstellung des Beweises der PKP-Unentscheidbarkeit | 452 |
| 9.4.4 | Übungen zum Abschnitt 9.4 | 458 |
| 9.5 | Andere unentscheidbare Probleme | 459 |
| 9.5.1 | Probleme bei Programmen | 459 |
| 9.5.2 Unentscheidbarkeit der Mehrdeutigkeit | ||
| kontextfreier Grammatiken | 459 | |
| 9.5.3 | Das Komplement einer Listensprache | 462 |
| 9.5.4 | Übungen zum Abschnitt 9.5 | 465 |
| Zusammenfassung von Kapitel 9 | 466 | |
| Kapitel 10 Nicht handhabbare Probleme | 469 | |
| 10.1 | Die Klassen V und MP | 471 |
| 10.1.1 | Mit polynomialem Zeitaufwand lösbare Probleme | 471 |
| 10.1.2 | Beispiel: Der Kruskal-Algorithmus | 472 |
| 10.1.3 | Nichtdeterministischer polynomialer Zeitaufwand | 476 |
| 10.1.4 | Ein NP-Beispiel: Das Problem des Handlungsreisenden | 477 |
| 10.1.5 | Polynomzeit-Reduktionen | 478 |
| 10.1.6 | NP-vollständige Probleme | 480 |
| 10.1.7 | Übungen zum Abschnitt 10.1 | 482 |
| 10.2 | Ein NP-vollständiges Problem | 483 |
| 10.2.1 | Das Erfüllbarkeitsproblem | 484 |
| 10.2.2 | SAT-Instanzen repräsentieren | 485 |
| 10.2.3 | NP-Vollständigkeit des SAT-Problems | 486 |
| 10.2.4 | Übungen zum Abschnitt 10.2 | 493 |
| 10.3 | Ein eingeschränktes Erfüllbarkeitsproblem | 493 |
| 10.3.1 | Normalformen für Boolesche Ausdrücke | 494 |
| 10.3.2 | Ausdrücke in KNF konvertieren | 495 |
| 10.3.3 | NP-Vollständigkeit von CSAT | 498 |
| 10.3.4 | NP-Vollständigkeit von 3SAT | 503 |
| 10.3.5 | Übungen zum Abschnitt 10.3 | 504 |
| 10.4 | Weitere NP-vollständige Probleme | 505 |
| 10.4.1 | NP-vollständige Probleme beschreiben | 506 |
| 10.4.2 | Das Problem unabhängiger Mengen | 506 |
| 10.4.3 | Das Problem der Knotenüberdeckung | 511 |
| 10.4.4 | Das Problem des gerichteten Hamiltonschen Kreises | 512 |
| 10.4.5 Ungerichtete Hamiltonsche Kreise und das | ||
| Problem des Handlungsreisenden | 519 | |
| 10.4.6 | Zusammenfassung NP-vollständiger Probleme | 521 |
| 10.4.7 | Übungen zum Abschnitt 10.4 | 521 |
| Zusammenfassung von Kapitel 10 | 526 | |
| Kapitel 11 Zusätzliche Problemklassen | 529 | |
| 11.1 | Komplemente von Sprachen, die in MV enthalten sind | 531 |
| 11.1.1 | Die Sprachklasse Co-A/'P | 531 |
| 11.1.2 | NP-vollständige Probleme und Co -MV | 532 |
| 11.1.3 | Übungen zum Abschnitt 11.1 | 533 |
| 11.2 | Probleme, die mit polynomialem Speicherplatz lösbar sind | 534 |
| 11.2.1 | Turing-Maschinen mit polynomialer Platzbegrenzung | 534 |
| 11.2.2 Beziehung von VS und MVS zu früher definierten | ||
| Klassen | 535 | |
| 11.2.3 Deterministischer und nichtdeterministischer | ||
| polynomialer Speicherplatz | 537 | |
| 11.3 | Ein für VS vollständiges Problem | 540 |
| 11.3.1 | PS-Vollständigkeit | 540 |
| 11.3.2 | Quantifizierte Boolesche Formeln | 541 |
| 11.3.3 | Quantifizierte Boolesche Formeln auswerten | 542 |
| 11.3.4 | PS-Vollständigkeit des QBF-Problems | 544 |
| 11.3.5 | Übungen zum Abschnitt 11.3 | 550 |
| 11.4 | Sprachklassen basierend auf Randomisierung | 550 |
| 11.4.1 Quicksort: Ein Beispiel für einen zufallsabhängigen | ||
| Algorithmus | 551 | |
| 11.4.2 Ein auf Zufallsabhängigkeit basierendes Modell | ||
| einer Turing-Maschine | 552 | |
| 11.4.3 | Die Sprache einer zufallsabhängigen Turing-Maschine | 554 |
| 11.4.4 | Die Klasse 1ZV | 556 |
| 11.4.5 | In 7ZV enthaltene Sprachen erkennen | 558 |
| 11.4.6 | Die Klasse ZW | 559 |
| 11.4.7 | Beziehung zwischen VSP und ZW | 560 |
| 11.4.8 | Beziehungen zu den Klassen T^und MP | 562 |
| 11.5 | Die Komplexität des Primzahltests | 562 |
| 11.5.1 | Die Bedeutung des Primzahltests | 563 |
| 11.5.2 | Einführung in Modular-Arithmetik | 565 |
| 11.5.3 | Die Komplexität modular-arithmetischer Berechnungen | 567 |
| 11.5.4 | Zufallsabhängig-polynomiales Primzahl-Testen | 568 |
| 11.5.5 | Nichtdeterministische Primzahltests | 570 |
| 11.5.6 | Übungen zum Abschnitt 11.5 | 573 |
| Zusammenfassung von Kapitel 11 | 574 | |
| Literaturverzeichnis | 577 | |
| Stichwortverzeichnis | 587 | |
A
Abgeschlossenheit Boolesche Operationen 166
Differenz regulärer Sprachen 172
Durchschnitt regulärer Sprachen
170, 171
Durchschnitt und kontextfreie
Sprachen 332, 336
Homomorphismen einer regulären
Sprache 174
Homomorphismen über einer kontext- freien Sprache 331, 338, 339
Hüllenbildung mit kontextfreien
Sprachen 331
inverse Homomorphismen einer
regulären Sprache 176
inverse Homomorphismen über einer
kontextfreien Sprache 337
Komplementbildung regulärer
Sprachen 168
kontextfreie Sprachen 328, 336, 337
reguläre Operationen mit regulären
Sprachen 168
reguläre Sprachen 166
Spiegelung einer kontextfreien
Sprache 332
Spiegelung einer regulären Sprache
173, 174
Substitution in kontextfreien
Sprachen 328, 329, 330, 331
Vereinigung kontextfreier
Sprachen 331
Vereinigung regulärer Sprachen 167
Verkettung kontextfreier Sprachen 331
Ableitungen linksseitige 213
mithilfe einer Grammatik 210
Notation 213
rechtsseitige 213
Satzform 216
Adelman, L. 563
Alphabete Begriffsdefinition 54
Potenzen 54
Assoziativgesetz Mengenvereinigung 148
Verkettung 148
Ausdrücke reguläre 59
rekursive Definition 48
Ausführungszeit exponentiell 472
Kruskal-Algorithmus 475
polynomial 472
Automaten endliche 59
B
Backus, J. W. 579
B aums truktur en kontextfreie Grammatiken (kfG) 219
Terminologie 220
Beobachtungen 42
Beweise Äquivalenz von Mengen 38
Aussageformen 34
Beschreibung formaler Techniken 28
deduktive 28
durch Gegenbeispiele 42, 43, 60
durch Widerspruch 33, 41, 60
Genau-dann-wenn-Aussagen 35, 60
induktive 29, 43, 60
kontextfreie Grammatiken (kfG) 217
Kontraposition 39
Reduktion auf Definitionen 32, 33
Wenn-dann-Aussagen 34, 59
Binärcodes
Turing-Maschinen 422, 423
Boolesche Ausdrücke Erfüllbarkeit 484
Normalformen 494
c
Carmichael-Zahlen 569
Chomsky, N. 24, 231, 311, 580
Chomsky-Normalform (CNF) 311
Definition 353
Zeitkomplexität von Umwandlungs- verfahren 343
Church, A. 367
Church-Turing-These 367
Cook, S. 24, 481
Cook, Satz von 486
CYK-Algorithmus 347
D
DEA siehe Deterministische endliche
Automaten (DEA) Deduktive Beweise
Begriffsdefinition 59
DeMorgansche Regeln 496
DeMorgansches Gesetz 170
Deterministische endliche Automaten (DEA)
Definition 71
Minimierung 198
Notationen 74, 75
Sprache 79, 111
Standardnotation 79
Startzustand 72
Tupel-Notation 72
Übergangsdiagramme 74, 75
Übergangsfunktion 72, 78
Übergangstabellen 74, 75
umwandeln in NEA 187
umwandeln in reguläre Ausdrücke
128, 129, 130, 131
Verarbeitung von Zeichenreihen 72, 73, 74
Deterministische Pushdown-Automaten
(DPDA) 289
Diagonalisierungssprache 424
Distributivgesetz 38
bei Mengen 149
Dokumenttypdefinition (DTD) 238
E
Endliche Automaten deterministische 71
nichtdeterministische 82
Entscheidbarkeit
kontextfreie Sprachen 341
reguläre Sprachen 185
Sprache 442
Zeitkomplexität 186
Epsilon-Übergänge 101
Erfüllbarkeit
Boolean Satisfiability (SAT) 484
Fermats Satz kleiner 569
letzter 358
Floyd, R. W. 580
G
Gegenbeispiele, Beweise 60
Genau-dann-wenn-Aussagen 35, 60
Gischer, J. L. 577
Gödel, K. 367
Grammatiken
endliche Automaten 27
kontextfreie 59
Greibach, S. 316
grep 114
H
Halteproblem 377, 433
Hamilton-Circuit Problem (HC) 512
Hello, World-Programm 357
Homomorphismen 174
HTML (HyperText Markup Language) 236
Identitäten 148
IDs (Instantaneous Descriptions) 369
Induktionsbeweise 43
Induktionsprinzip 44
Inferenz, rekursive 210
K
Kantenüberdeckung 511
Karp-Vollständigkeit 481
Pushdown-
Kellerautomat siehe
Automaten Kernighan, B. 357
k-konjunktive Normalform
(k-KNF) 494
Klausel 494
Kleenesche Hülle 115
Knotenüberdeckung 511, 512
Kommutativgesetz der Mengen- vereinigung 148
Konfiguration 369
Konjunktive Normalform (KNF) 494
Konkatenation 55
Kontextfreie Grammatiken (kfG) 207
Kontextfreie Sprachen (kfS) 206
Kontraposition 39, 60
Konversion 40
Kruskal-Algorithmus 472
Kryptographische Systeme Problemklassen 530
Las-Vegas-Algorithmus 559
Lesk, M. 578
lex 143, 144
Literale 494
M
Markup-Sprachen 235
McNaughton, R. 577
Mehrdeutigkeit Grammatiken und Sprachen 245
inhärent 252
Eliminierung 256
Unentscheidbarkeit 367
Mengen
Distributivgesetz der Vereinigung von
Mengen 38
Kommutativgesetz der Vereinigung von Mengen 38
Minimum Weight Spanning Tree
(MWST) 472
Modifiziertes Postsches Korrespondenz- problem (MPKP) 449
Modulararithmetik 565
Monte-Carlo-Algorithmus 557
N
Nichtdeterministische endliche Automaten (NEA)
Äquivalenz mit deterministischen 88
Begriffs definition 111
Definition 85
Eliminierung von Zuständen 131
erweiterte Übergangsfunktion 86
informelle Darstellung 83
Minimierung 201
mit Epsilon-Übergängen 103
Sprache 87
Textsuche 98, 99
Übergangsfunktion 83
umwandeln in DE A 186
umwandeln in reguläre Ausdrücke 131
Nichtdeterministische Turing-Maschine
(NTM) 391
Nichthandhabbarkeit 470
Problemklasse NP 477
von nichtdeterministischer TM in polynomialem Zeitaufwand lösbare Probleme 476
zufallsabhängige Sprachklassen 550
Node-Cover Problem (NC) 511
NP-Vollständigkeit 471 3SAT-Problem 503
Beweise 505
Komplemente von NP-vollständigen Problemen 531, 532, 533
o
Ogdens Lemma 327
Operatoren Annihilator 148
Einheit 148
idempotente 150
reguläre Ausdrücke 115
Stern- 115
Vereinigung 115
Verkettung 115
Vorrangregel 120
Parsebäume Ergebnis 221
kontextfreie Grammatiken (kfG) 219
Parser 231
YACC 234
Postsches Korrespondenzproblem (PKP) 446
Definition 446
Primzahltest 562
Probleme 3SAT 493
auf Zufallsabhängigkeit
basierende 553
Begriffs definition 57
Boolean Satisfiability (SAT) 480
CSAT 498
Definition als Sprache 58
Erfüllbarkeit Boolescher
Ausdrücke 483
Gerichteter Hamiltonscher Kreis 513
Hamiltonscher Kreis 477
Handlungsreisender 520
in polynomialem Platz lösbare 534
Ja-/Nein-Formulierung 510
Klasse Co-NP 530
Klasse NP 476
Klasse NPS 574
Klasse P 471
Klasse PS 530
Klasse RP 551
Klasse RPP 530
Klasse ZPP 551
Klassifizierung 24
Knotenüberdeckung 511
mit polynomialem Platz lösbare 535
mit polynomialem Speicherplatz
lösbare 534
mit polynomialem Zeitaufwand
lösbare 471
MWST (Minimum Weight Spanning
Tree) 472
nicht handhabbare 470
nicht von Computern lösbare 356
NP-harte 480
NP-vollständige 480
NP-vollständige erfüllbare 527
Problem des Handlungs- reisenden 477
quantifizierte Boolesche
Formeln 534
Reduktion 362
Traveling Salesman Problem
(TSP) 477
unabhängige Mengen 506
unentscheidbare 359
USAT 532
von NTM in polynomialem Zeit- aufwand lösbare 476
zufallsabhängige 550
Produktautomaten 68, 170, 172
Programmiertechniken Turing-Maschinen 379
Unterprogramme 383
Pseudozufallszahlen 550
PS-Vollständigkeit Beweise 541
Definition 540
Problem quantifizierter Boolescher Formeln 544
Pumping-Lemma 232
Anwendungen 162
Definition 160
für kontextfreie Sprachen 319
Pushdown-Automaten (PDA) 260
Q
Quantifizierte Boolesche Formel
(QBF) 541
Quicksort-Algorithmus 551
R
Reduktion 362
mit polynomialem Zeitaufwand 478
Richtung 365
unentscheidbare Probleme 436
Reguläre Ausdrücke algebraische Gesetze 147
Annihilatoren bzgl. Operatoren 148
Anwendungen 114
äquivalenten DEA konstruieren 122
äquivalenten NEA konstruieren 131
Äquivalenz von Ausdrücken 147
Assoziativität 147
aus endlichen Automaten 134
Auswertungsreihenfolge der
Operatoren 120
bilden 117
Definition 117
deterministische endliche Automaten
(DEA) repräsentieren 122
Distributivgesetze 149
Einheit bzgl. Operatoren 148
grep 114
Gültigkeit algebraischer Gesetze
prüfen 151
Idempotenzgesetz 150
Kommutativität 147
Komponenten 117
lexikalische Analyse 114
nichtdeterministische endliche Auto- maten (NEA) repräsentieren 131
Operatoren 115
Sprachen 118
Sternoperator 115
Textmustersuche 144
Unix-Notation 140
Verhältnis zu endlichen Automaten 122
Rice, Satz von 442
Ritchie, D. 357
Rivest, R. 563
RSA-Codes 563
Savitch, Satz von 539
Schubfachprinzip 94
Shamir, A. 563
Spiegelung
kontextfreie Sprachen 332
Sprachen Begriffsdefinition 56
Beispiele 56
Beschreibung durch
Mengenvorschrift 57
Beschreibung von Problemen 58
Beweis der Nichtregularität 160
Co-NP 531
deterministische endliche
Automaten 111
deterministische Pushdown-
Automaten 291
Diagonalisierungs- 424
Kleenesche Hülle 115
Komplemente rekursiv
aufzählbarer 427
Komplemente rekursiver 427
kontextfreie 462
nicht rekursiv aufzählbare 421,
423, 425
nicht rekursive 427, 428
Präfixeigenschaft 291
Pushdown-Automaten 270
reguläre 79
reguläre Ausdrücke 114
rekursiv aufzählbare 377
rekursive 427
universelle 430
universelle und Unentscheid-
barkeit 433, 434
Vereinigung 115
Verkettung 115
T
Table-filling-Algorithmus 193
Tautologien 532
Teilmengenkonstruktion 88
Textsuche 97
invertierte Indexe 97
Thompson, K. 578
Turing, A. M. 24, 357, 360, 367
Turing-Maschinen 356
Äquivalenz zwischen ein- und
mehrbändigen 388
Ausführungszeit 390
Begriffsdefinition 59
beschränkte 396
Bewegung 368
Binärcodes 422
Eingabealphabet 368
endliche Steuerung 368
endliche Zustandsmenge 389
erweiterte 386
Halteproblem 377
ID (Instanteneous Description) 369
Konfigurationen 417
Kruskal-Algorithmus 474
Las-Vegas- 560
leere Sprache 438
Leerzeichen 368
mit mehreren Bändern 386
mit mehreren Spuren 417
mit mehreren Stacks 400
mit polynomialer
Platzbegrenzung 534
Monte-Carlo- 560
nicht rekursiv aufzählbare
Sprachen 421
nichtdeterministische 391
Notation 368
polynomiale Länge der Eingabe 530
Probleme hinsichtlich Spezifikationen 444
Problemklassifizierung 366
Programmiertechniken 379
Rechenzeit 413
semiunendliche Bänder 397
Simulation durch Computer 407
Simulation von Computern 409
Sprache 376
Stackanfangsmarkierung 401
Übergangsdiagramme 373
Übergangsfunktion 369
unentscheibare Probleme 436
Unentscheidbarkeit 360
universelle 430
Unterprogramme 383
Zählermaschinen 403
Zeitkomplexität 390
zufallsabhängige 552
zweidimensionale 396
u
Übergangs diagramme 74
Begriffsdefinition 111
Pushdown-Automaten 264
Turing-Maschinen 373
Übergangsfunktion 85
deterministische endliche Automaten
(DEA) 72
erweiterte 75
nichtdeterministische endliche
Automaten (NEA) 83
Turing-Maschinen 369
zufallsabhängige Turing- Maschine 555
Übergangstabellen 75
Umkehrung, Beweise 60
Unentscheidbarkeit 362
Begriffs definition 466
kontextfreie Sprachen 462
Mehrdeutigkeit kontextfreier
Grammatiken 459
Modifiziertes Postsches Korrespon- denzproblem (MPKP) 449
Postsches Korrespondenzproblem
(PKP) 446
Reduktion von Problemen 365
rekursiv aufzählbare Sprachen 426
rekursive Sprachen 428
Satz von Rice 442
Turing-Maschinen 436
universelle Sprachen 433
Unix
reguläre Ausdrücke 140
w
Warshallsch-Algorithmus 187
Wenn-dann-Aussagen 34, 59
Widerspruch, Beweise 41, 60
x
XML (eXtensible Markup Language) 231, 238
Dokumenttypdefinition (DTD) 231
Y
YACC-Parsergenerator 234
Yamada, H. 577
z
Zählermaschinen 403
Begriffsdefinition 418
Leistungsfähigkeit 404
Sprache 404
Zeichenreihen
Begriffsdefinition 54, 60
Konkatenation 55
Länge 54
leere 54
Verkettung 55
Zeitkomplexität Äquivalenz von regulären Sprachen
bestimmen 191
Entscheidbarkeit regulärer
Sprachen 186, 189
polynomiale 476
Turing-Maschinen 390, 391, 471
Wechsel zwischen Repräsentationen
regulärer Sprachen 187
Zugehörigkeit zu regulärer Sprache bestimmen 190, 191
Zufallsabhängigkeit Turing-Maschine 552
ZW 559
