Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Warning: preg_replace(): Compilation failed: this version of PCRE is not compiled with PCRE_UTF8 support at offset 0 in /web/Sites/BlickinsBuch.de/functions.php on line 241 Blickinsbuch.de - Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit - John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
     Artikel werden geladen

    Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit

    Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit

    Autoren:

    Verlag:
    Pearson Studium  Weitere Titel dieses Verlages anzeigen

    Auflage: 3., aktualisierte Auflage
    Erschienen: März 2011
    Seiten: 592
    Sprache: Deutsch
    Preis: 49.95 €
    Maße: 170x241x33
    Einband: Taschenbuch
    Reihe: Pearson Studium - IT
    ISBN: 9783868940824

    Register

    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