Autoren-Aufruf! Ich habe seit Jahren keine Zeit und Lust mehr, die Inhalte von Mandalex zu pflegen, weswegen sie teilweise veraltet und inkorrekt sind. Wenn ein Wikipedia-Autor über diese Seite stolpert und Lust hat, meine Texte irgendwie in Wikipedia zu integrieren, darf er oder sie mir eine Email schreiben, ich würde die einzelnen Seiten dann gerne abgeben, auf dass ich die Seite irgendwann schliessen kann. Und bevor die Frage kommt: Nein, ich zahle nichts.
Hier sind einige gängige Abkürzungen der theoretischen Informatik, sowie die einige Symbol-Belegungen aufgelistet.
Abkürzungen und Worterklärungen
| FSM | Finite State Machine |
| FA | Finite Automaton |
| DFA | Deterministischer Finite Automaton |
| NFA | nicht-deterministischer Finite Automaton |
| deterministisch | klar definierte Übergänge (jeweils nur 1 Möglichkeit) |
| nicht-deterministisch | unklare Übergänge (mehrere Möglichkeiten oder spontan) |
| probabilistisch | unklare Übergänge mit Wahrscheinlichkeitsverteilung |
| e | steht hier für epsilon |
| e-frei | ohne spontane Übergänge |
| e-Hülle | alle States, die durch spontane Übergänge von einem State aus erreichbar sind (inklusive der State selbst). |
| PowerSet | States bestehend aus allen möglichen Kombinationen von States = 2^S Beispiel {}, {1}, {2}, {1,2} für 2 States |
| CA | Counter Automata |
| PDA | Pushdown automata |
| NPDA | nicht-deterministischer Pushdown automata |
| LBA | Linear bounded automata. Doppelseitig begrenzter Speicherplatz |
| CFG | Kontext-freie Grammatik |
| CFL | Kontext-freie Sprache |
| TM | Turing-Maschine |
| ambiguous | vieldeutig |
| recognizable | erkennbar: Es gibt eine TM, die alle Wörter, die in der Sprache enthalten sind, als solche erkennt. Sie muss aber die nicht enthaltenen nicht unbedingt als falsch erkennen! Terminiert nur für enthaltene Wörter immer. |
| decidable | entscheidbar: Es gibt eine TM, die alle in der Sprache enthaltenen Wörter als solche erkennt und alle nicht-enthaltenen nicht akzeptiert. Terminiert immer. |
| computable | Das Gleiche wie decidable, wird aber eher benutzt, wenn das Resultat keine boolsche Funktion, sondern ein Wert ist. |
| total function | Funktion zu der es eine TM gibt, die für alle möglichen Einganssignale terminiert. |
| TM acceptor | TM, die entweder haltet und dabei akzeptiert oder nicht, oder aber loopt |
| TM decider | TM acceptor, der stets haltet. |
Grammatik und Sprache:
Grammatik:
| G(V,A,P,S) | Grammatik |
| V | Variablen, nicht-terminal-Symbole, grammatikalische Typen |
| A | Alphabet, terminal-Symbole |
| S | Startsymbol, ein Element aus V |
| P | Produktionen der Form L -> R, wobei L und R eine Zusammensetzung von Faktoren sind |
| (V OR A) | Faktor |
| w | Wort, besteht nur aus Terminalsymbolen = A* |
| epsilon | Nullstring, "", nichts |
Sprache:
| L(G) oder L | Sprache { w Element von A* | S ->* w } |
| L* | beliebig viele Wörter der Sprache |
| U | Union, Zusammenlegung |
| ¡ (Kreis) | (Kon-)Katenation, Hintereinandersetzung |
Definition von akzeptierten Wörtern:
| * | beliebig viele |
| + | beliebig viele, aber mindestens 1 |
| ( ) | Klammerung |
| | | oder |
| e | Abkürzung für epsilon: der leere String |
Beispiel: 1*(0|1)11* = 01, 11, 101, 111, 011, 111, 1101, 1111, 1011, 1111, ...
Maschinen und Automaten
| M=(S,A,f,s0,...) | Automat, Maschine, Die Punkte stehen für Erweiterungen |
| S | Menge von Zuständen S x A -> S |
| A | Alphabet, Eingangssignale |
| f | Menge der Übergänge |
| s0 | Start-Zustand |
| F | Akzeptoren F Teilmenge von S |
| g | Transducer, Rückmeldung |
