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
Artikel werden geladen
Autoren:
Verlag:
Pearson Studium Weitere Titel dieses Verlages anzeigen
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