Next:
Deterministische (endliche) Automaten
Up:
Formelsammlung theoretische Informatik I
Previous:
Backus-Naur-Form 25
Contents
Index
Reguläre Sprachen (Typ 3)
27
Subsections
Deterministische (endliche) Automaten
Definition
27
Zustandsgraph
27
Sprache eines DFA
29
Grammatik zu einem gegebenen DFA
30
Nichtdeterministische (endliche) Automaten
Definition
30
Zustandsgraph
Sprache des NFA
31
Vom NFA zum DFA - Potenzmengenkonstruktion
32
Vom NFA zum DFA - effizientere Methode
Von einer Grammatik zum NFA
35
Reguläre Ausdrücke
36
Das Pumping Lemma
39
Äquivalenzrelation und Minimalautomat
42
Definition Äquivalenzrelation
42
Algorithmus Minimalautomat
46
Abschlusseigenschaften
48
Entscheidbarkeit
49
Wortproblem
Leerheitsproblem
Endlichkeitsproblem
Schnittproblem
Äquivalenzproblem
Marco Möller
18:11:27 24.10.2005
