Next: About this document ...
Up: Formelsammlung theoretische Informatik I
Previous: Entscheidbarkeit 90
Contents
- Äquivalentzklassen
- Definition Äquivalenzrelation 42
- Überführungsfunktion
- Definition 27
- Abgeschlossenheit
- Konkatenation
- Ableitung
- Ableitungen 14
- Ableitungsbaum
- Syntaxbäume 23
- Abschlusseigenschaften
- no title
| no title
| no title
- Aequivalentzproblem
- Entscheidbarkeit 78
- Aequivalenzproblem
- Entscheidbarkeit 90
- Alphabet
- Definition
- Alphapet
- no title
- Arbeitsalphabet
- Definition 81
- Assoziativität
- Konkatenation
- asymptotischen
- Komplexitätsfunktionen (O-Notation) 189 /
- Backus-Naur-Form
- Definition 13
| no title
- Berechnungsrelation
- Definition 81
- Beschreibungsmittel
- no title
- Blank
- Definition 81
- BNF
- Backus-Naur-Form 25
- Chomsky Normalform
- no title
- Chomsky-Hierarchie
- no title
- CNF
- Chomsky Normalform 53
- CYK-Algorithmus
- no title
- Determinismus
- no title
- deterministisch
- Deterministisch kontextfreie Sprachen 76
- deterministisch kontextfrei
- Deterministisch kontextfreie Sprachen 76
- Deterministische Automaten
- no title
- DFA
- Definition 27
- DPDA
- Deterministisch kontextfreie Sprachen 76
- EBNF
- Backus-Naur-Form 25
- Eingabealphabet
- Definition 27
| Definition 30
| Definition 67
| Definition 81
- Eingabewort
- Definition 27
| Definition 67
- endliche Automaten
- no title
| no title
- Endlichkeitsproblem
- no title
| Entscheidbarkeit 78
- Endzustaende
- Definition 81
- Endzustandsmenge
- Definition 30
- Endzustände
- Definition 27
- entscheidbar
- Typ 0 oder rekursiv
- Entscheidbarkeit
- no title
| no title
| no title
- Ergänzung
- no title
- erweiterte BNF
- Backus-Naur-Form 25
- Genaue Schranke
- no title
- Grammatik
- no title
| Definition 13
- Graph
- Zustandsgraph 27
- Greifenbach Normalform
- no title
- Halbgruppe
- Konkatenation
- Hillel
- Das Pumping Lemma 39
| Das Pumping Lemma (uvwxy-Theorem)
- Hopcroft
- Algorithmus Minimalautomat 46
- Häufungspunkt
- no title
- Hülle
- Relationen auf Sprachen 187
- Index
- no title
- inhärent mehrdeutig
- Typ 2 oder kontextfrei
| Typ 3 oder regulär
| Syntaxbäume 23
- Kelleralphabet
- Definition 67
- Kellerautomaten
- no title
- Kellersymbol
- Definition 67
- Komplement
- Abschlusseigenschaften 48
| Abschlusseigenschaften 89
- Komplexitätsfunktionen
- no title
- Konfiguration
- Definition 67
| Definition 81
- Konkatenation
- no title
| Wort
- kontextfrei
- no title
- deterministisch
- Deterministisch kontextfreie Sprachen 76
- Kontextfreie Sprachen
- no title
- kontextsensitiv
- no title
- Kuroda Normalform
- no title
- LBA
- Linear Beschränkte Turingmaschinen 84
- Leerheitsproblem
- no title
| Entscheidbarkeit 78
| Entscheidbarkeit 90
- Leerzeichen
- Definition 81
- linear beschraenkt
- Linear Beschränkte Turingmaschinen 84
- Linksableitung
- Syntaxbäume 23
- LR(k)
- Deterministisch kontextfreie Sprachen 76
- Mächtigkeit
- Definition
- mehrdeutig
- Typ 2 oder kontextfrei
| Syntaxbäume 23
- Metaregel
- Backus-Naur-Form 25
- Metasymbol
- Backus-Naur-Form 25
- Minimalautomat
- no title
- Monoid
- Konkatenation
- neutrales Element
- Konkatenation
- NFA
- Definition 30
- Nichtdeterminismus
- no title
- nichtdeterministisch
- Ableitungen 14
- Nichtdeterministische Automaten
- no title
- Normalformen
- no title
- NP-hart
- Äquivalenzproblem
- O-Notation
- no title
- Obere Schranke
- no title
- PDA
- Definition 67
- Produkt
- Abschlusseigenschaften 48
| Abschlusseigenschaften 62
| Abschlusseigenschaften 89
- Produktionen
- Definition 13
- Pumping Lemma
- no title
| no title
- Rechenschrittrelation
- Definition 67
- Rechtsableitung
- Syntaxbäume 23
- reflexiv
- Relationen auf Sprachen 187
- Regeln
- Definition 13
- regulär
- no title
- Reguläre Ausdrücke
- no title
- Reguläre Sprachen
- no title
- rekursiv aufzählbar
- no title
- Relationen
- no title
- Satzform
- Ableitungen 14
- Schleifenlemma
- Das Pumping Lemma 39
| Das Pumping Lemma (uvwxy-Theorem)
- Schnitt
- Abschlusseigenschaften 48
| Abschlusseigenschaften 89
- Schnittproblem
- no title
| Entscheidbarkeit 90
- Schranke
- no title
| no title
| no title
- Sprache
- Definition
| no title
- Sprachen
- no title
- Startkonfiguration
- Definition 67
| Definition 81
- Startsymbol
- Definition 13
- Startzustand
- Definition 67
| Definition 81
- Startzustandsmenge
- Definition 30
- Stern
- Abschlusseigenschaften 48
| Abschlusseigenschaften 62
| Abschlusseigenschaften 89
- Symbole
- no title
| Definition
- symmetrisch
- Relationen auf Sprachen 187
- Syntaxbaum
- Syntaxbäume 23
- Syntaxbäume
- no title
- Terminalalphabet
- Definition 13
- Terminalwort
- Ableitungen 14
- TM
- Definition 81
- transitiv
- Relationen auf Sprachen 187
- Tupel
- Wort
- Turingmaschine
- no title
- Ueberfuehrungsfunktion
- Definition 67
| Definition 81
- Ullmann
- Algorithmus Minimalautomat 46
- Untere Schranke
- no title
- uvw-Theorem
- Das Pumping Lemma 39
- uvwxy-Theorem
- no title
| Das Pumping Lemma (uvwxy-Theorem)
- Variablen
- Definition 13
- Vereinigung
- Abschlusseigenschaften 48
| Abschlusseigenschaften 62
| Abschlusseigenschaften 89
- Wort
- no title
- Wortproblem
- no title
| Wortproblem 21
| no title
| Der CYK-Algorithmus 64
| Entscheidbarkeit 78
| Entscheidbarkeit 90
- Zeichen
- Definition
- Zustände
- Definition 27
| Definition 67
- Zustandsüberführungsfunktion
- Definition 27
- Zustandsgraph
- no title
- Zustandsmenge
- Definition 30
| Definition 81
- Zustandsminimalen
- Algorithmus Minimalautomat 46
- Zustandsüberführungsfunktion
- Definition 30
- Äquivalenzklassen
- no title
- Äquivalenzproblem
- no title
- Äquivalenzrelation
- Relationen auf Sprachen 187
| no title
- Überführungsfunktion
- Definition 30
Marco Möller 18:11:27 24.10.2005